My main failure (as always!) was that I would tend to build up and cross the Channel too cautiously/ too late. Also, because of the Celts' starting position, it often takes a long time to contact the eastern Barbarian-Civs, so I usually also forgot to get anyone to fight extended campaigns against Eastern Rome, so they would usually win on VPs.
The main problem with this Scenario is that the Civ3-AI tries to play as if it was a normal epic-game: the large amount of colonisable space tempts them into racing to fill up the map with Cxx(x)xC'd towns, which, combined with the large swathes of Hills and Forests (and their perennial disinclination to build enough Workers!), means that they aren't able to grow/defend a lot of those towns effectively, leaving them very vulnerable to the city-elimination mechanic, which they don't "understand".
Arguably, all you have to do to beat half of them is to station stacks of 2-3 (fast) units around your borders to watch out for passing AI Settler-pairs, follow them until they found a town, and then (declare war and) capture it...
AFAIK, losing towns to flips doesn't count towards the elimination-limit, only losing them to conquest does