Server resourse issue with large forum

[SteveC]

I have a site that has a small number of users but has been around for several years so we have a lot of posts. Here are the stats

Threads: 32,607, Posts: 547,854, Members: 2,235, Active Members: 201

I'm currently hosted by Rochen. About a week ago, my forum started getting really slow at certain times of the day. They tell me it's because I have too many posts and when someone does a search by clicking on "new posts" it overwhelms the server. Here are the specifics of what they are saying:

the server is actually being overwhelmed, you queries are consuming 10-20X the resources (Disk I/O) permitted at any given time on a shared plan by our AUP (2% of overall system resources over a 24 hour period). Your scripts are performing full table scans or joins that are too large to fit in memory, and the result is a significant amount of disk I/O.

They've given me 48 hours to prune 75% of my posts, which I don't want to do because I don't want to lose them or move to another host.

Is there anything I can do to reduce the server load? Can posts be archived so they aren't part of a search query? Or is there a way to make searches only look at the last month or so of posts unless a user specifies otherwise?

Or do I need to move to a dedicated server? If so, any suggestions of who to go with?

thanks!