These sorts of problems aren't solved by uninformed guesses from people with no access to the server. They're solved by expert assessment of server and database logs, analysis of the database itself and trapping and examination of queries e.g. via the mysql slow query log. There's a reason why they can charge 150 euro an hour for this expertise.

What service are they providing for you? Is this shared hosting, a VPS, a managed server, an unmanaged dedicated server? Is the mysql server on the same server as your web server or a dedicated mysql server? Why the heck are you running your Zen Carts on a windows server? The underlying theme of (most of) these questions is trying to establish who is responsible for keeping your mysql server running effectively.