I lost a Sludge Bomb TM on my Emerald because that dick doesn't cough it up until you come back later. I'd advise you to come back for it as soon as you get Fly so you don't forget.
I'm almost positive you can pick it up immiediatly after getting surf, if you take the swim to take advantage of the trainers levels while your pokemon are still close to them.