Act 2008 Premium Reporting Slowness

I'll try to give as much detail as possible here.  

I'm currently trying to solve a fairly significant problem regarding a networked ACT 2008 setting.  
One of the goals on this ACT install was for upper level management to be able to essentially "one-click" and pull up reports.  Many of the managers are incredibly computer illiterate and will absolutely not accept anything else.  I realize this is a working restriction and not a necessary limitation of the software, but it informs the problem.  

Essentially, when anyone tries to do a "Notes/History" report, it will never complete if "All Contacts" are chosen.  It doesn't matter if there's only 1 result or if there are hundreds -- it just sits there.  On a query with only 20 results, I let it run for well over 7 hours on 3 different computer setups -- no dice.

Three different ACT! consultants have suggested narrowing down the search results through an advanced query in order to decrease the lookup size.  The reports WILL run in this instance.  In fact, if the reports are narrowed in any way, it will run appropriately.  It's only when all contacts is selected that it won't complete.  Unfortunately, the advanced query solution is considered dead in the water and "unacceptable," even with saved queries.

Details up front to help rule things down:

1) I had nothing to do with the decision or implementation to use ACT, so suggestions to switch products aren't going to work (this is the most common solution given to me -- I recommended a different product from the beginning due to reviews of the most recent ACT 2008 version).  This decision came from far above.
2) The following problem occurs even after a full re-install on all networked computers.
3) It occurs on a multitude of computers types including, but not limited to: PIV 3.6 Ghz, multiple 1.8 dual cores, and three darned powerful servers.  All have 2 gigs of RAM or greater (in the case of the servers, much more).  All computers are running XP or 2003 Server.  
4) It occurs on the default 10.0.0.x version, and on the 10.0.1.x and 10.0.2.x updates
5) It occurs on both directly connected computers and on computers with their own remote databases.
6) The "main database" will be over 10,000 records at start (will grow to over 100,000 records quickly).  There it's unusable.  But on a database with only 1800 records it has the same result.

Is this normal for ACT 2008?  If so, is there any way around it?  

If it isn't normal, are there any suggestions on how it might be fixed?

Besides what is listed above, I've tried repairing and re-indexing the databases, creating new databases, granting users full permissions settings, applying all ACT! 2008 updates, and have made sure that neither the processor, RAM, nor network throughput was in any way bottlenecked.  

Any help would be greatly appreciated, even if it's just saying this is normal MO for the program.