I just found it in Alpha Sapphire! I wasn't even looking because that would be insane. Did they change the encounter system for Feebas from the original game?
Edit: Looks like they did. There's now a 5% chance of encountering Feebas on any tile. Carry on, then!