Scrub that - to save edited orders in admin and avoid the Payment Method Required problem you simply need to Re-Apply the Payment AND Shipping Methods each time you go into the admin edit order totals tab. The process of writing a patch highlighted this problem of these fields becoming unset so maybe this will help someone create a fix to this problem once and for all.
I guess this could be fudged by automatically adding calls to Apply Shipping and Apply Payment Methods on displaying the totals tab each time
I have therefore removed the link to the patch as it would create more problems, allowing unset payment methods and shipping methods
After trying everything here with no luck I came up with a simple vqmod that patches this problem. It simply removes the controller check for Payment Method in the admin panel edit orders but does not change the same check when a customer adds orders. I can't think of where this would be a problem AFAIK only admin can edit orders?
HOWEVER, This highlights another problem that the shipping methods and payment methods actually become unset on editing the order despite the dropdowns displaying the previously set value. So you MUST re-set the shipping method and payment methods by clicking the Update buttons next to the dropdowns.
1) Only tested with 126.96.36.199 using latest vqmod (installed using AE Pro Vqmod manager although FTPing should work same)
2) Use this at your own risk, this is designed to be a temporary patch until an official patch is released
3) Remember to Re-Apply Shipping and Payment Methods every time you edit an order, It appears that this can be done Before OR After clicking the Save button.
I am very disappointed that this problem has persisted so long, so posted this so that others can at least edit orders which can be an absolutely crucial feature for some.