The last Pokémon you battle before going back to the area where you want to encounter Mew is important. That Pokémon's Special stat decides what you encounter.
I'm unsure how randomizer settings may change this though, I've not tried it in a randomizer.