Why don't you just dump the SEO company and find an SEO specialist that uses Xara? Sounds to me that's what you need to do

Frankly if they were even half-competent they would have bought a copy of WD (not expensive) and hey-presto, they SEO your site and any other Xara-designed sites, they're useless, dump them