So what did we actually do? Programmers, read on. Humans, feel free to skip the rest of this post and move straight on to trying it out.
Our recent releases have been focused on adding functionality and the whole thing just got very heavy and bloated. Memory was leaking because apparently Adobe Flex isn't really meant for creating thousands of recursive controls over and over again. The worst part was the latency - if you've navigated into a task that contained many sub-tasks it would take them a while to load which was very frustrating and it slowed you down. That dog won't hunt. We learned that one of the slowest things you can do in Flex is to add and remove elements from the display list. So now we don't. We recycle and hide unused elements instead of adding/removing them. That also took care of the memory leaks, since apparently we cannot rely on Flex to properly dispose of unused objects (even [sigh] when the Flex Profiler itself shows no paths to those objects from the GC root).
Rendering tiny zoomed-out sub-tasks was rewritten in lower-level Flash graphics (as a C++ developer it sounds odd to me - "low level Flash"... but I'm getting used to it). This approach worked great when we implemented Team View so we adopted in the other views as well.
So how noticeable is the difference? Quite noticeable. We measured how long it takes to drill down from the top of a large plan to the bottom-most "leaf" task and it took about one third of the time. So roughly 3x as fast. But that's mainly because the built-in animation simply takes its time (about 400ms) - without it navigation just seems jumpy and weird. When we profiled just rendering time we saw a 10x improvement.
Hopefully you'll notice this too.