I don't use this feature of sales orders, so this may not be too precise, but I looked at the code and it looks like it's checking in the TABLE_SO_PAYMENTS and TABLE_SO_REFUNDS to see if those payment types are used.

My guess is that when you deleted the order, you may have done this through the stock Customers->Orders instead of Customers->SuperOrders. If this is the case, the order was removed from TABLE_ORDERS, but still exists in those other tables.

I'd probably manually remove the one record from the TABLE_SO_PAYMENTS table using PhpMyAdmin - assuming that this record is associated with a non-existant order ID anyway.