I've been using a Grass Knot Uxie to reliably take on Rhyperior, and it's definitely a great switch in to almost any Rhyperior set. The most common ones I see are Rock Polishers, who only do about 65% with a Jolly Life Orb Megahorn, and Substitute users, who do even less. Grass Knot on Uxie is also rather unexpected, unlike Mesprit.
Rhyperior definitely is one of the best pokes in this metagame though, switching in with no problems into nearly all normal types, walls like Spiritomb and Registeel, and countless Choice users. Actually beating it is really not too hard. It's mainly a case of predicting the Stone Edge or Earthquake and acting accordingly as Legacy Raider said (and Megahorns are really predictable). I can see how it troubles many teams, but I mostly use offensive pokemon, and Rhyperior doesn't get many chances vs. offensive teams with the low special defense and numerous weaknesses. Basically, if you're overly reliant on things like Chansey, Registeel, and Spiritomb, Rhyperior's going to wreck you.
I've been seeing a lot of surprisingly offensive Spiritomb, and damn these are hard to take out and defend against. There are crazy things like mixed sets with Shadow Ball/Pursuit/Will-O-Wisp/Shadow Sneak, along with typical moves like Sucker Punch, Pain Split, Calm Mind, and Rest over Shadow Sneak sometimes. Some have bee running Spooky Plate to get the most out of Shadow Ball and Sneak sometimes, which feigns a Band sometimes, and proceeds to destroy switch ins. Trick users are annoying too. Definitely a pokemon I want to try out sometime.
EDIT: Pratty, I think that Fire Punch wins here. Fire Punch would hit two of Marowak's main counters harder than any other move: Tangrowth and Leafeon. The only two things that I can think of that Double Edge would hit better than any of Marowak's other moves are Claydol and Weezing, who aren't as common as the grass types. Generally, Earthquake is better than Bonemerang because of accuracy issues, unless you really hate Substitutes.