Quick answer: Try including the extra 4 digits of your full zip code in the address you have saved in the Wallet app. Your bank might be using this 9 digit zip code to verify things as opposed to the normal 5 digit zip code.
This was absolutely infuriating and took over an hour to resolve. Hoping this post helps someone else save some time. I was trying to transfer Apple Cash to my PNC Debit card and kept getting "Address Verification Failed" despite no issues in the past. After logging in to see what PNC actually had as my address I noticed they stored my address with the full zip code consisting of 9 numbers (e.g. "44567-1234"). With that info I then turned back to the Wallet app and updated my address to include those extra 4 numbers in the zip code field and then everything worked. Note: After entering the normal 5 numbers of the zip code, once you type the hyphen ("-") the Wallet app will turn the field red as if it has an error. Just keep typing the last 4 numbers after the hyphen and the field will then turn back to normal.