The normal way to delete an installed application is to go under Start>Settings>System>Remove Programs. This should do a proper uninstall and clean up the registry.
If you just want to wipe out the icon that appears in your Programs group, point your file explorer to Windows>Start Menu>Programs and delete the shortcut.
Voicemail icon should clear when it gets a signal from your carrier. Try leaving yourself a voicemail, then calling back in and checking it. That should force the signal to clear the notification. If it doesn't, then you may need to contact your carrier to ensure that the notification is properly enabled for voicemail.
I'm unfamiliar with PDAnet, but if you're running WM6 (or upgrade to it) it's a non-issue. All you have to do under WM6 is open "Internet Sharing", plug in your USB cable and click "connect". Your PC will automatically detect your Treo as a network device and you're free to browse the web.
NOTE: ATT/Cingular charges extra for a "tethered" data plan. However, if you upgrade with the Unbranded ROM you can still do it with a standard data plan. The thread for the unbranded WM6 rom (which will install on any brand treo) is over here:
http://www.everythingtreo.com/forum/...isd-13690.html