An alternative will be the CDSEO mod of Website cm:
Requirements:
1. Apache web server
2. Apache support for ForceType and AcceptPathInfo
http://www.websitecm.com/x-cart-mods/x-cart-seo-links.html
But moving to a new host would also be an option. Look for the recommended hosts of X-Cart. They all are very good.