Technically what you said you lost the battle, so instead of going in again, use your Eevee to fly to Route 5 or Mt. Moon, and look everywhere to find it. You might run out of PP again, so I suggest a PP up, which you can find in Silph Co, Routes 13, 16 and 21, the Rocket hideout or the Pokémon Mansion.
Also since I can't write on walls YET, I would suggest SlowkingButFast. (slowking is not slow)