I have installed VSTFS on a machine using the local admin. Now the machine is added to the domain and the local admin account is deleted. After which I am unable to login to VSTFS using Team Explorer or the web console.
How can I readd a new admin or create more users?
See the KB article Move Team Foundation Server from One Environment to Another.
It's not an entirely trivial procedure, and ideally, you'd have backed up your data prior to joining the domain, but it seems you should be able to have your TFS install back in working order with some work.
As with anything related to TFS installation, this kind of thing should be much, much easier with TFS2010. If you're planning to upgrade anyway, this might be a good opportunity to simply back up your data, uninstall your current TFS and install the 2010 version -- the upgrade scenario is delightfully simple:
You can perform an in-place upgrade by doing an upgrade on the same hardware that was running the earlier version of Team Foundation Server. When you use this path, you must uninstall the previous version of Team Foundation Server, install Team Foundation Server 2010, and then run the upgrade wizard.
Not 100% sure if this would automagically restore your administrator login to working order, but it's worth giving it a try...