I continued filling the Hoenn Dex on Emerald today by doing the Regi sidequest, beginning with catching a wild Wailord on Route 129. The other night I searched for the best part of half an hour for one with a Level 35 Pokemon as my lead and Max Repels activated, and couldn't figure out why they weren't appearing. I gave up until today after doing research and discovering that Wailord actually appear at Levels 25-30, and sure enough my very first encounter happened to be a Level 30 Wailord! Given the high encounter rate of Tentacool and a 1% chance of finding a Wailord, i'd say I was very lucky.
After opening the three caves, I made my way to Regirock's cave in the desert route and to my surprise I caught it with ease. However, my run of luck seemed to be coming to an end thereafter when I encountered Registeel. The steel golem bolted out of approximately 35 Ultra Balls and 15 Great Balls as well as a Timer Ball and a couple of Poke Balls until, rather fortuitously, an accidentally thrown REPEAT Ball caught it. That is one battle I am sure to remember for years to come. I ended my progress today by saving in front of Regice.