It's January 2013, and I'm having this problem with VM 2.0.18a on Joomla 2.5.8. When I try to delete a test order, I get:
vmError: Seems the used shipmentmethod got deleted
vmError: TableOrders delete Order shipmentTable = #__virtuemart_shipment_plg_ `virtuemart_order_id` = 19 dbErrorMsg
vmError: VirtueMartModelOrders::remove 19
Order could not be deleted.
I did not change shipment methods or anything else between creating the test order and attempting to delete it. Hopefully the developers will add this to the bugs to be fixed