All I can say it, I share your pain. Verified by VISA and its counterpart, MasterCard SecureCode are useful tools to reducing (not eliminating) online fraud.
Basically a cardholder is required provide identifying information such as address/phone number, last for digits of checking account tied to debit card, CVV code, etc. The cardholder can then create a password that they will use at any participating merchant to complete an online purchase.
Unfortunately for the bank, any of this information can be phished, stolen via Trojan computer virus, used by roommate, etc.
Reg E and VISAs zero-liability still apply regardless of the bank's chargeback rights. An alternative to a chargeback in this case is to send a "Retreival Request" to the merchant. This is a non-finanical request that requires the merchant to at least provide you with information about the transaction such as IP Address where the order was placed, name and address where merchandise (if any) was shipped. At least then you will have more information to determine if the cardholder did in fact benefit from the transaction, or if it was truly fraud.
If the merchant fails to comply with the request, this opens up chargeback rights to the bank for "failure to supply requested information." Occaisionally I have recovered funds in this way.
Bottom line is that in the event this is fraudulent purchase, you must reimburse the cardholder and file a report with Visa's Fraud Reporting System (FRS).
I can do all things through Him who gives me strength. (Phillipians 4:13)