I usually take Vera Cruz, Villa Hermosa, Campeche, Havana, St. Augustine, and San Juan before I start chasing the Baron. This severely cuts down on the towns he can go to, so I can usually catch him in the tavern once or twice per game. It makes it much easier to deal with him.