max_questions - is max number of SQL queries allowed per hour. This is not necessary a physical server limit but rather a quota sever admins have set up. It's not very fair of them saying that you need to buy bigger server to handle more requests. No matter how fast the server is, the limit won't let it make more queires for your site.
Of course a good job of SQL queries optimization and cache can be performed if you find someone who can do it for you. But I would recommend changing a hosting company anyways.