some of these selects are making joins from 3-5 tables and that's probably slows MySQL down.

Yepp, IIRC most indices on the 'later' tables in a join aren't used by MySQL (read that in the annotated html-manual).

You may consider splitting the 5-lines-long select into smaller ones implementing the join logic in perl, that should provide a noticable speed-up gained by local changes to the perl-code.
Coupled with a cache this should make things smooth for times to come. Implementing a cache without a db-speedup would be IMHO a half-legged solution, as some visitors would have to wait the 10+ secs on a cache-miss.

regards,
Tom