Currently Deleting a Shipping Method removes it from the table. This breaks orders that had this shipping method set, and may also break shipping categories, etc.
If you have a cart in progress, you loose the ability to move around the cart. I believe it also breaks the ability to see it in the admin.
I think the best solution to this is to set a "deleted_at" flag that disables it from being used. This will maintain the relationships and history.
I agree. I've seen this error come up a couple of times myself.
Soft-delete shipping methods when they are deleted through admin backend