Yes, they should, yet I've been unable to locate them at times; I think you're right, that there are occasions when they DON'T appear.
Whether that actually happens (I'm not positive that it does), my fallback approach is view/toolbars/circular (which ALSO should have automatically appeared - but I seem to recall times it too didn't!!). Viewing the toolbar in itself should spawn one [more] generation of arrows. (To my recollection, that last step always works.) Even if there STILL aren't any, you can navigate to the affected cells via the toolbar, and alt-t-u-d or alt-t-u-t.
Extra info: there are obscure VBA functions to create the arrows - with the bonus of applying to an entire range; the menu one only works for single cells. Holler if you want that.
One theory on why the arrows would not appear is because a workbook is extensive and is pushing the calculation limits - i.e., the number of dependencies. AAR the status bar never fails to work, ensuring that anyone looking over your shoulder will conclude you're a circular-referencing ninny!