I'm having some similar problems, so I figured I'd jump onto this thread and see what everyone thinks.
First, the URL: http://www.scarabproductions.ca/catalog
I have disabled the "IP to Host Conversion Status" option, and things didn't really seem to speed up.
Even the admin login page is slow to load, and it has to be the most lightweight page possible. The admin area is slow, etc.
The part of the domain not used by the store (http://www.scarabproductions.ca) loads very fast, so I have isolated this as either a PHP or mySQL issue, or possibly both. Now I'm handy with computers, but far from a expert - particularly with servers, etc.
I have complained to my host and they essentially said that if it isn't the cart package that's provided in my hosting plan, then they won't support it. We went back and forth and I told them that it's not the cart that needs support, it's your hosting that is painfully slow. They're just ignoring me now. :) Essentially I gave up and I'm ready to pull the plug and switch hosting companies (poor performance is one thing, poor customer service is another), but I'd like to see if there's anything that I can do because I'm not sure if I can spend the time to switch hosts for a few weeks.
Any tips would be greatly appreciated!
James