[MOSS2007] Search issues due to corrupt SSL certificate

After installing MOSS2007 which has Service Pack 1, the Infrastructure Update and the August Cumulative Update slipstreamed I ran into the following issue:

My environment consists of one Index server and two Search servers. When opening the new Search Administration page, it is supposed to list the status of all of the index and search servers. Unfortunately the Search servers were listed as Error. After doing some more investigation I found the following error appear in the application log of both search servers each minute:

Event: 6482
Type: Error
Source: Office SharePoint Server
Category:Office Server Shared Services

Application Server Administration job failed for service instance Microsoft.Office.Server.Search.Administration.SearchServiceInstance (aa8a83f6-ff42-4be3-ae6c-c1cb2205cc8f).

Reason: The underlying connection was closed: An unexpected error occurred on a send.

Techinal Support Details:
System.Net.WebException: The underlying connection was closed: An unexpected error occurred on a send. ---> System.IO.IOException: Authentication failed because the remote party has closed the transport stream.
at System.Net.Security.SslState.StartReadFrame(Byte[] buffer, Int32 readBytes, AsyncProtocolRequest asyncRequest)
at System.Net.Security.SslState.StartReceiveBlob(Byte[] buffer, AsyncProtocolRequest asyncRequest)
at System.Net.Security.SslState.ForceAuthentication(Boolean receiveFirst, Byte[] buffer, AsyncProtocolRequest asyncRequest)
at System.Net.Security.SslState.ProcessAuthentication(LazyAsyncResult lazyResult)
at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state)
at System.Net.TlsStream.ProcessAuthentication(LazyAsyncResult result)
at System.Net.TlsStream.Write(Byte[] buffer, Int32 offset, Int32 size)
at System.Net.PooledStream.Write(Byte[] buffer, Int32 offset, Int32 size)
at System.Net.ConnectStream.WriteHeaders(Boolean async)
--- End of inner exception stack trace ---
at Microsoft.Office.Server.Search.Administration.SearchApi.RunOnServer[T](CodeToRun`1 remoteCode, CodeToRun`1 localCode, Boolean useCurrentSecurityContext, Int32 versionIn)
at Microsoft.Office.Server.Search.Administration.SearchApi..ctor(WellKnownSearchCatalogs catalog, SearchSharedApplication application)
at Microsoft.Office.Server.Search.Administration.SearchServiceInstance.Synchronize()
at Microsoft.Office.Server.Administration.ApplicationServerJob.ProvisionLocalSharedServiceInstances(Boolean isAdministrationServiceJob)

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.

When I tried to open the SearchAdmin.asmx page (http://<index or search server name>/SearchAdmin.asmx), I get a page cannot be displayed.

This issue is caused by a corrupt SSL certificate on the "Office Web Services" web site. To solve this issue, you have to create a new certificate. You can use the SelfSSL tool, included in the IIS resource kit.

Run the following command on all search and index servers:
selfssl.exe /N:CN=<server> /K:1024 /V:9999 /S:951338967 /P:56738