Oh are they doing snail mail verification? If so, that's much better. I don't remember having to do a verification when I added addresses to my account.
I believe there are some other ways. I recently added a new address and did not need to verify. I called and was told that If the name was the same as the one on the account with an already verified address and had received I believe it was 3 packages at the new address within the last 30 days it automatically verified.