I think I had something similar, though that was, I believe, due to a PayPal module and PayPal Express payment. The customer had different addresses in the shop and with PayPal and the one in PayPal warranted free shipping, but the shop address didn't. Might this be a similar problem with the Adyen module?