Hello,
I actually own a web hosting company (www.etwebhosting.com), so I can recommend myself to you.

We have about 3000 customers and have been in business since 2001. All our customers came to us from word-of-mouth referral, so we are definately doing something right. I'm sure if you give us a chance, you'll be very happy. (We offer a 30-day money-back guarantee...)
You can find a special SnippetMaster discount and free license offer here: http://www.etwebhosting.com/specials/snippetmaster.html
>> If they do install Zen Optimizer, do I have to reinstall Snippetmaster Pro?
No. Well... maybe. It really depends on if they have changed anything else besides just removing the Zend Optimizer software from your server. If they have modified your website "file path" structure, then you might need to edit/modify each of the users in SnippetMaster so that they are correct with the new path information. (Same for any Upload Groups you have created...)
Let me know how things go.