Update I managed to solve it by getting my user granted permissions to remotely connect to the desktop using credential set 2 and thus being able to remove the stored credentials from Credential Manager.
I log onto my server with one set of credentials and open Visual Studio 2012 using "Run as different user" (Shift + Right-click) as I need a second set of credentials to deploy to my dev. env. SharePoint site.
I have previously done above and then connected to TFS using a third set of credentials, as the my user (second set credentials) didn't have access yet. Now my user have access and I wish to use these credentials instead.
TFS automatically logs me in with the third set credentials every time I open VS using "Run as different user" - However, if I open VS normally without using "Run as different user" I get prompted for login to the TFS.
I have tried checking the Windows credentials and there is nothing there. And I can't log onto the server using the second set credentials as only the first set can access the server with Remote Desktop.
So how do I "clear" cached TFS credentials when using "Run as different user"?
Go to control panel > User Accounts > Manage Your Credentials > select your Team foundation Server and choose remove/edit - viola! Next time you go into Team Explorer you will be prompted for a new set of credentials.