In short it sounds like a MEID issue, either on the phone or on the account. Also note Verizons network knows what phone it is as soon as the browser is used or any other apps that access the internet.
Now on another note, please take a second to read through the forum rules about MEID repair. We're on thin ice but as long as it keeps on track there won't be a problem.