Why would recovery moves dominate? They've also got only 3 PP. Stall teams would be really helped, because they can afford to run bulky spinners and spinblockers, and hazards would own in this metagame. I foresee Toxic being pretty useful too, as a single use of Toxic does more than many weaker offensive moves, while the stronger ones run out of PP quickly. (Aside-Rapid spin still has plenty of PP). And SubRoost Zapdos would be interesting, although I think it'd need to carry Chestorest or something, because 3 PP of Roost isn't great. (Also, Stall teams might have Recover+Rest, or such.) Poison Heal 'Scor would be pretty great because it doesn't waste PP healing if it doesn't want to, and while Protect PP runs out fast, you can use it to chip away at, say, Ice Beam or Surf PP. SubTect would be interesting for PP stall, but more than not you'd probably just see a lot of switching. (Of course, you could take advantage of it by Toxic'ing a lot. And remember, Heal Bell should only have one use!)
Now, sure, a stallmon can stall out your strongest move and then not really be breakable. But now he can't heal either, and he usually relies on healing. So it's almost a wash. Meanwhile, if you have multiple moves that can hurt him, it's a net loss. So an interesting option could be like I often do ingame-carry a weaker STAB alongside a stronger one, for PP purposes. After you've been stalled by, say, a Jellicent (Cursed Body won't be too good in this metagame, where PP is liable to run out before you can disable the move), you can just unleash the weaker move and watch him fall. Or pokemon with pretty wide coverage that can afford to have a moveslot slashed will be more viable. I also think Forry will be pretty beastly in this metagame, although Gyro Ball runs out quick. Still, pair him with a Suicune and watch as his counters suddenly can't touch him.
Now Regenerator... THAT will dominate.
Edit:SubRoost Aerodactyl could be pretty great, actually. Like Zapdos, but he can suicide lead if you like and set rocks, and if switching really is going to be so prevalent, having rocks up as fast as possible could be really helpful. Meanwhile, he can also Taunt to block enemy rocks from going up, also helpful in this kind of a metagame.
Also, Zoro:Psybeam, from what was said above, has 6 PP? And Psychic has three. Seeing as Psybeam=65 and Psychic=90, it's clearly not a case in that instance. I'm sure there are plenty of other examples.
Stall teams probably would still be great mind you, but powerful wallbreakers could get through them, just because if you only have 1 check to a pokemon, it can get through you via killing your Recover PP.
Double Edit: Uh, Pillsbury, couple ways around that. First is T-spikes, which gets many of them. Second is just SR and Spikes and Phazing. Thirdly is having a good Rapid Spinner and just switching around. Let them stew in their own PP juices.
Of course, those teams would have a bulky spinblocker and maybe a grounded poison-type/spinner, but in a metagame where recovery runs out quickly, you can definitely muscle through spinblockers. Although the metagame might revolve a little around Pressure Subtecters and those that set up hazards on them.
Also, Harvest Exxegutor. #LeppaBerry. So weather would be good to counteract that, and seeing as weather MOVES have 1 PP, most teams will need a way to deal with that. I'm actually thinking multi-hit moves will be popular as hell in this metagame, as will Leppa Berries.