I also experienced this address verification issue in April 2024.

The way I solved it was by using an address lookup website that checks if my address exists. I just had to change my zip code to a different one for the area, and change my street address to match the valid format for the address website (valid format seems to be [Street Number, Street]). You may have to abbreviate Street as St, like 12 Greenhill Street vs 12 Greenhill St