And of course, try upgrading. :-) Most modules get faster over time rather than slower, and Drupal 5 is faster for anonymous users than 4.7. Once on Drupal 5, make sure you use the CSS compressor. I've been able to cut a page's load time in half just by switching on the CSS compressor. Drupal 6 will include a Javascript compressor as well for the same reason.
How does one enable the CSS compressor? I don't see any docs in drupal.com about this.
Thanks!