1. If you have version 4.1.x, that means you've been using xcart for at least 4 or 5 years. That means you should have a "free" x-payments NFR license - but you need to "install" it somewhere in the next 36 hours! Like right now!!!! It's use it or lose it. Read this:
http://forum.x-cart.com/showthread.php?t=65370
2. A good x-cart specialist host, such as Hands-on or EWD can solve most of your issues without spending silly $$$$
Store upgrade costs for designers should have nothing to do with fundamental hosting issues.
If you "own" an x-payments NFR license, RUN, don't walk, and find a host with php 5.3 right this minute. Install it. Tell x-cart where it is installed and you save yourself $1189. But you MUST do that right now. Today. That is assuming you've been a long-time x-cart customer.