This is really a server question and not particularly Wordpress.
You're running into a MySQL server speed bottleneck at 1and1. Sorry, but they're well known as a slow shared host, and for that reason I doubt their VPSs are any better.
Caching and a CDN will only do so much for you. You need more horsepowwer in the form of a better and faster MySQL server, and if you're already paying for a VPS, move to a better VPS host, like Media Temple.
Once there, with root access, you can use a utility such as mysqltuner.pl to log and analyze the performance of the MySQL server and adjust server memory and database query cache parameters in the configuration file my.cnf. You will also be able to adjust apache - in httpd.conf - to handle high loads.
There is little sense in trying to optimize the database queries made my Woo Commerce or Wordpress; any changes made will need to be made again after updates.