I have a whole list old addresses from the "Navigation" app, that I need to delete off of my phone, but no one from Verizon knows how.
If these are "starred" places, you'll have to unstar them. Just
If these are just locations that are popping up in the recently found list when you start typing a name/address then you can try clearing the app data to delete that. Home -> Menu -> Settings -> Applications -> Manage applications -> Navigation -> Maps -> Clear data.
Bookmarks