This is what I get:
My address is residential and I have even tried 2 different (home and office) address and get the same message. I tried different formats, all cap, periods, no periods, spelled out Street, made sure the format phone number was exactly the same even thought Shopify insisted in automatically switching it to (123) 456-7890.
I actually did this for my business but it turns out it violates the community guidelines Google lists because my business operates solely online. I am also experiencing this issue where I am not able to print shipping labels because my address is "not verified." How do I fix this issue when I merely rent a mailbox at the business address I list? I don't know what to do.
I would first make sure your address appears at the link above, and then if it doesn't contact Shopify support.
The next option would be to change your address to something that is accepted Shopify only uses this address to estimate the shipping costs, so changing it to something near your address is fine.