I’ve switched hosting to Media Temple’s managed WP hosting which seems to have fixed the issues.
I have a feeling that my previous hosting company knew it was their issue, but didn’t know how to resolve it, as every other test pointed in their direction.
Not sure about accessing your site through localhost though…
