Slow queries and wp_postmeta file causing fair use with my hosting company

I have a 75000 listing directory set up. My query’s are running very slow. If I choose a category it’s slow to get to the search page, but when I drill down to the detail page it is very, very slow. I just got a service notice from my provider from only 645 queries on my post_meta file. They said it must have junk entries but when i cleaned it and optimized it it didn’t change much at all.

For 73,898 rows in my wp_posts I have a post meta file that is 1328356 rows in my post_meta table. The post_meta table is 77.3MB with an index length of 40.2MB. I need to keep the service provider fair use police off my back, but I really would like to speed up my searches.

Any ideas?

Thanks in advance,
Bob@BobJean.com