Oh okay, that is different then.
In that case I only recommend maybe trying the stop-words feature. That could potentially still result in 10-20% savings in the database space. You can still run a OPTIMIZE TABLE command, but those are also issue by Ajax Search Pro so the table should not be defragmented.
If I may suggest something regards your hosting: If the “weakest” point of your overall server is the database, then instead of going for a completely new hosting plan (which usually scales up everything), you can probably get away by hosting only the database separately. If your main site hosting does not need to much CPU horsepower, nor storage, then placing the database to a separate plan is usually faster. It is not as simple as one click hosting, but if you have experience with VPS and Unix it is definitely worth it.