I found the solution to this problem by noticing that the 'deleted' Database Connections only re-appear in Server Explorer when I open the Solution file (previously, I had VS set to open the last project on start-up).
So, knowing it must be something in the solution, I searched the files and I have a Database Project which holds build scripts, etc. In this project, within the *.dbp file, there is a "DBRefFolder" section. The 'deleted' database references were here, and when I deleted them, all was well.
It is a bit annoying that VS doesn't remove these entries properly, but at least I have a solution.
Below is an sample extract from the *.dbp file:
Begin DataProject = "SQL Server Databases"
...
...
...
...
Begin DBRefFolder = "Database References"
Begin DBRefNode = "Name"
ConnectStr = "Data Source=XXX;Initial Catalog=YYY;Integrated Security=True"
Provider = "{91510608-8809-4020-8897-FBA057E22D54}"
Colorizer = 6
End
...
...
...
...
End
End