So after much fighting with code over the past few days, I finally had an idea that I tried that finally worked after talking to gamesquest1 which lets me now patch everything cleanly. The final patch will be distributed as a single xdelta (a program to help with the patching process will be included). Currently the patch is around 2.42mb but will probably grow a little bit before the final patch. There will be no need to create xorpads or anything of that sort anymore!
For the people who showed interested in the patch setup that I mentioned writing, here it is:
http://www.mediafire.com/download/q1v5akelzmxq5ua/patch.rar
You'll need to modify the patch.bin to point to all of the right filenames (see top of bat file). The other part that will need to be patched for other games is the "Patch RomFS files" section. That is where the code to run xdelta or copy your data goes. Everything else should work on most games.