[banden]

Well if you're rooted, and if you have the latest sprecovery, I believe you can do the factory wipe without the need to remove your apps.

Also, you can create backups of your apps, only thing is that you won't get updates on the paid ones.

Third, you can try contacting the developers of the paid apps and outline your situation. They may even be able to individually resolve this for you as well. Most of the community that I've dealt with are outstanding.

Good luck.