130 MB for a database is actually small. The method of searching in 6.5x is different and can tax the resources more perhaps but there is something more going on then meets the eye I'd think.

I've been using this site for 3 years now. Not cheap but has been a good host provider for me.

http://midphase.com/html_files/hosting_plan.php

They say that MySQL can be up to the size of my space which is 35GB

You probably don't have access to actually run some MySQL commands to maybe re-index or repair possible issues on your database.

If you upgrade to the new UBBT 7.x it uses the MySQL FULLTEXT search that when fully and properly implemented returns from a search for me with about 400MB of post data and 9 years in about 1 second.

So an upgrade in board software might be another option, but seems your host provider is really the one being a whiner about it and you might be better off switching.

.