I thought that’s the problem (I saw that in other community article), I tried without +4 zip explicitly but no luck at that time. So here is what I tried before vs today
Before (When I saved address, with same billing address checkbox checked)
I tried 2 things. One without +4 zip code and with +4 zip code.
Reason: When you enter the address, modal pops up and it suggest with +4 zip code, so I did that. The reason I tried without it is I saw the that somebody resolved the issue removing that. Here is the article.
This time (When I removed saved address, with same billing address checkbox checked)
I tried with +4 zip code. Same as before, when I entered address, it suggests with +4 zip code. Pressed check out after I enter credit card information (issued 3 days ago and just recieved), and tada, it works.