This feature request is our second highest voted issue (JRA-4446), and one that I personally want to see fixed. For the moment, there is a 3rd party plugin that solves most use cases (Structure Plugin from ALM works).
The key for us as a vendor is making it work without degrading the overall experience. We have seen plenty of other issue trackers implement this, but it really detracts from the overall experience when you don't know what is a task, or a project, or a feature etc.
But we're definitely trying to find a solution.
On FishEye - we have it working on code bases that have hundreds of millions of lines of code, but it often requires some tuning. For example (and one of many such examples), in older versions of Subversion, there was no real way to tell what was a branch, and we rely on 'conventions' such as /branches/ to tell this.
Unfortunately, every code base contains 'mistakes' where someone copied the entire tree into /branches/ or created a branch somewhere else.
There are some easily configured settings that usually make FishEye run a lot faster but explicitly telling it about some of these cases.
But - even saying that, performance was around 50% of the last few releases of FishEye, so the latest versions do run significantly faster in all instances.