SharePoint 2010: The Security Token Service is not available

This problem has been reported mostly from SharePoint 2010 beta 2 due to the missing of Hotfix KB 976462. SharePoint 2010 RTM has this hotfix included in the prerequisite as you can see it from window updates off control panel. so don't bother to download and install again:

But occasionally this problem occurs even to RTM sharepoint 2010.  The sharepoint Health Analyzer report it only as warnings, but it is actually a fatal error as it results in failure of all claim aware services such as search service, for example: When a user start searching, WFE needs to talk to Search query componet, and if the Search query is hosted in a different server, WFE needs its local STS to collect claim, and then sends the claim to Search query component Server. Obviously unavailability of STS on WFE will break things totally.

What is the fix then? STS is neither a SharePoint service, nor a window service, but actually a WCF web service, so first to check IIS if this web service or its application pool is running, and if they are, try to restart and if that still does not solve the problem. You need to re-provision STS service application. The STS service application is provisioned during sharepont configuration, and is not clickable from UI:

But it can be re-provisioned from Powershell:
$sts = get-spserviceapplication -identity {id of sts}
$sts.status  
online
$sts.provision()

Additionally, disconnecting servers from farm and rejoining them can also fix this STS problem.