Yes Verio is a terrible registrar (actually they don’t handle the actual domain registrations, it’s done through Melbourne IT who are a really terrible registrar), but relying on automatic renewal and notices is also a very bad policy. I recommend renewing all domains well in advance, for example I review my domain list every January 1 and July 1, then you won’t ever have to worry about this happening.
Anyway, I really don’t understand why you would have to pay the domain pirates anything, this type of thing used to happen in the past but it doesn’t happen any more because virtually every registrar has policies in place to prevent re-registration within a certain time-frame after expiration. For example here is Verio’s page regarding their policy :
http://www.verio.com/support/documents/view_article.cfm?doc_id=3675
It seems to me that you shouldn’t have had to pay anybody that re-registered the domain after expiration, it shouldn’t even have been possible according to Verio’s “Redemption Period” policy. Time to bring out the lawyers!