A few days ago we had a sudden SQL Server reboot of the server hosting the TFS databases. Though I still have to determine the cause of that, it had a nasty side effect. When the crash occurred a deployment of a build to a lab environment was in progress. This caused the lab environment to stay in the deploying state even though the build was stopped and even deleted.

To fix things I had to dive into the actual table holding the Lab environment information of your project collection (called LabEnvironments in your project collection database).

The problem was that there was still a BuildUri value in the record for my Environment. After deleting that (and seeing one more build fail). Things were back to normal again.