WOW.... I was having this issue and the Wordpress forums were a massive mess, with no one having a clue about this... always blaming a server setup.

I am glad there is a solution... I ended up going with a fast VPS with tons of resources due to non-WP script needs, and that solved this problem, but it was a mess for several weeks on 2 hosts (one of which was hostgator).