Just my two cents worth here. Ray examined my set up and for some reason the "license" was trying to check for accuracy on each page load, instead of once a month. When Ray fixed this the speed was a 1000% faster. No hesitation at all. Might be worth a look. Just a fyi for the troubleshooting file. My cart went from 4.0 to 4.5 during development.
Hope this helps.