At the places where it's failing, did you happen to see if there were any payment processor logos on the terminals' displays? It might be only a specific processor or two with botched software and/or connection to Visa.