Honestly, if you're at 'thousands of formulae' across multiple sheets, I'd probably suggest writing a graph based execution engine too.

The circular reference thing would have definitely thrown me for a loop though.