Your phone already have native sync with most Google Apps, such as GMail, and Calendar. The Gmail syncing also takes care of your contact list as well as email. Verizon's sync doesn't work I don't believe, and they haven't released an app for it on android. So, if you can export the data to a .csv, it should easily import into gmail/calender, then sync right up with the phone.
As for your POP3 question, it is impossible (well not impossible, but very involved) to have a message delete on both your phone and desktop. IMAP can do it, but not POP3. However, if you delete it on your phone before your desktop has downloaded it, it will be "deleted" in the sense your desktop will never download it. This is assuming you have delete from server checked in the options on your phone.