Really, there isn't much that could be wrong with the database itself, beyond table corruption. And if that were the case you'd get database errors. So there isn't anything you need to do on that end.
Since the temporary "problem" they had resulted in better performance for you, then it's definitely their MySQL server and the way it's being utilized.
The size of your forum definitely doesn't require a VPS. It sounds like it might just take a better host. We have many customers running boards larger than yours on hosts such as godaddy, just using their standard plan with no problems.
