One of our customer service reps took an order from an existing customer. He pulled up the customers record and asked if the address/cc had changed. The customer indicated there was a new address and our rep updated it on the manual order screen.
He then charged the customer/transmitted the CC info to our processor (PayPal). The charge was declined by fraud services as there was an address mismatch. When we looked up the order in Paypal, it had the old address in it.
Is it possible that by changing the address at the manual order screen that the new address wasn't yet committed back to the database prior to being transmitted to paypal?
Outside of user error I can't think of another explanation.
Are you sure the customer also updated the credit card address on the payment (or CCTerminal) tab? This is a separate address from the billing or shipping address, and doesn't update automatically...