Here's an (possibly heretical) idea:
How about charging a extremely nominal fee (e.g. $0.10-$0.15) per "All Forum" search?
As I understand it, the limitation at the moment is computing resource issue - presumably a seperate search server would need to be set up, to handle indexing, search requests, etc.
Charging a fee would cover those costs.
I know this is somewhat contrary to the prevailing philosophy of offering all FT resources for free to everyone. Yet, right now, with "everything free", we don't have a "All Forum" search option.
Just thinking outside the box...