All good advice.

But...

There is no way you could have got as far as you could if the hosting topped out at 20 queries. You just wouldn't ever have loaded a page. I am assuming that you have loaded a page in the past. So that figure just has to be wrong. ( Which obviously is another reason not to trust the hosting )

But it does perhaps suggest that there is a possibility that there is something amiss with your install of Zen. I only say a possibility because there are a lot of 'ifs' in the logic.

If the figure '20' is just wrong, then perhaps your installation is actually running a excessive amount of queries. Which could be due to all kinds of things like an add-on module that is messed up or some incorrect code or.... or..... or....

I am not saying that your proposed course of action is not the best. What I am saying is work with your new hosting right from the start to investigate the number of queries that normal operation of the site produces if you find there is no problem then all is good. If you do see that there is an issue then you can solve it rather than just postponing a headache. A good hosting company will help you with this and also Zen can display the number and time for queries at the bottom of each page, the setting for which is in admin>>configuration>>logging.