I tested my patience three times on Route 119, trying to hunt down a Feebas. The first time, I started about halfway down the river, and the second time, I started from the top of the river (or as far up as you can get before running into those bike bridges). I gave up both times out of boredom.
The third time, I started from the top of the river once again, and as luck would have it, ran into a Feebas-yielding tile before getting to the top of the first waterfall. I caught Feebas after Feebas there, trying to get one with a nature that would allow for an enhanced Beauty stat. I think it was around the 7th or 8th one that finally came up with an appropriate nature. Yes, I'm too lazy to breed them, which is why I caught so many of them on that one tile.
After that, evolving it into Milotic was fairly easy. I had been stockpiling the berries needed for Blue PokeBlocks for a while (I think I had been setting them aside for one of my Swamperts).
After all this work, I caught this Pokemon solely to complete my Hoenn Pokedex (which I did end up eventually completing)... but who knows, I may dig it out of my PC and give it a go in battle...