When they restored the DB from backup, they replaced it with a copy that didn't have the problem.
I suspect GD said they couldn't help because of this:
The wp_posts is too large to repair so you will need to edit locally and then restore to the database.
That's interesting, and I wish they'd said 'we can't' rather than 'It's not us.' It was your DB on their servers. While they weren't at fault (these things happen), it's frustrating and, IMO, a poor support experience. Even at 34k posts, I've run repairs on pretty big tables (I have a 400meg DB, it's got some killer tables). Still, there's a little bit you can do to help keep your DB size smaller.
First in your wp-config.php, add this:
Put it above the 'stop editing here' line and it will restrict WP to fewer revisions, thus keeping your DB smaller.
Now, make a backup of your whole Database before you go any further :)
You can run this code (from Lester Chan) in phpMyAdmin to clean up all your old revisions:
FROM wp_posts a
LEFT JOIN wp_term_relationships b ON (a.ID = b.object_id)
LEFT JOIN wp_postmeta c ON (a.ID = c.post_id)
WHERE a.post_type = 'revision'
Finally optimize the tables via phpMyAdmin, and you should have a (somewhat) smaller DB, which will make repairs more possible.
Oh and at 34k posts, you may need to upgrade to a bigger server anyway. Depends on the traffic, but that's a lot to query.