So after authoring this original topic, I disputed with EX and the debt came back validated. Apparently all Verizon had to do was say "yes" and it was validated.
I have been reading quite a bit about Planet Feedback so I gave it a shot. I left a message last week and had a call from Verizon corporate within 48 hours. After talking to the rep he informs me that he can't find proof so he is forwarding me to the "Recovery Dept". After about 3 days I get a call from the Recovery Dept and they say, "This account goes back to 2001 and we just can't find any information - we will be deleting it and sending you a hard copy for your files". Finally! This took forever.
Best news - even though this account was 6.5 years reporting my EX score popped up 91 points!
I am posting this as a testimonial - If it isn't yours, fight for your right and have them prove you wrong.
The most upsetting part of this is the fact that many at Verizon knew they didn't have a contract or proof - they just wanted to keep me down...