Something i noticed the other day was with the latest release of Cain is that it recovers deleted network connections (dialup, broadband, etc)
(maybe the feature has been there for a few releases, not sure, i don't check for updates on Cain that often )

Granted it only recovers usernames and passwords not the connection name, type, or dial in number (if it applies), and where im from it wouldn't be to hard to try a connection on allot of the dial-up ISP's, and dial-up is sill used more then broadband because broadband prices/coverage suck in Australia. (i still have adsl though lol). Also you could probably just enter some BS details on the last connection attempt, and windows will store that instead, haven't tested, but im guessing it would work.

But, Does anyone know of ways to remove all traces entirely of deleted connections?

http://www.winguides.com/registry/display.php/124/

This might help you.

hmm, i like to have my passwords saved though, just dont want traces of old/other connections.

but i will play around with it when i get to a point i can either log out and/or reboot

i.e. enable it, reboot, and see if it removes them all, or if Cain can still find the old connections, just with no password, or if Cain can find old conenctions with old passwrods, but new/current conenctions only have user name, etc, etc.

Was kind of hoped someone knew of a app that did it, well, cain can read/find it, so must be able to remove it somehow without using policys