I don't want to mess anything up...
I think that that's 100% the right attitude to have. Being careful can save you lots of grief and you do want to play it safe.
I found the php myadmin page. Am I supposed to check ALL the tables and then press "repair tables"?
Yes. If there's a table in need of repair then selecting all the tables would be the correct thing to do.
Also, will this make my site go down temporarily?
I've never seen it do that (take it down) but your problem is odd, and you are getting a lot of visitors so read on.
This problem you are having is odd and annoying, but nothings on fire and your blog isn't down. Some posts are showing up as 404 and that's not really "the sky is falling!"
So do this: make those back ups (harmless to do), read those links on restoring your database, and sleep on it (assuming you're in the western hemisphere).
Tomorrow speak with your hosting company. 9,000 visitors per hour is not a small number and your host may be spreading your database over multiple servers. When you look at your blog, you see the missing posts. When I looked at that example post, I got a 404.
So ask them this: "Why is it that someone in NY gets a 404 page not found but Google and I can see that missing post without a problem?"
If they're using a Mysql database spread over many locations, some of those locations may not be right. Or it could be something else, ask them and see what they say.
So sorry for all the questions!
No worries, it's a volunteer support forum. You will be obligated to respond to other forum questions that you can answer, but only in a non-obligatory way. It's cool like that.