Playing at Emperor, I found the best way to win this was basically to MA all the Barbarian tribes surrounding the 'other' half of Rome to attack that half, and then MA with whoever was left to go after 'my' half.
Although I've never
won as the Celts, in every game I've played as them, it's been relatively easy to get Western Rome destroyed by signing MAs with the Franks, Saxons and Visigoths (or the Ostrogoths? One of the -goths, anyway!). I'd take out the Roman towns in Britain, and they'd take down enough of them on the mainland, that when I was ready to start moving units over there myself, I'd only need to grab another 1-2 towns to finish them off. 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...
I don't know, whether flipped towns count towards the 8 town elimination?
AFAIK, losing towns to flips doesn't count towards the elimination-limit, only losing them to conquest does