Mirroring after restoring the database on a new machine
Certificate based authentication of Database Mirroring is explained in How Does Certificate based Authentication Work. After your server rebuild you should had open the master database database master key (hic!) using OPEN MASTER KEY ENCRYPTION BY PASSWORD=... and then add the new server service master key encryption to it using ALTER MASTER KEY ADD ENCRYPTION BY SERVICE MASTER KEY. Then DBM would had access to the endpoint certificate private key and would successfully authenticate with the partner.

If you do not have the original master database master key password (shame!) then you need to force a new one, which may loose the DBM endpoint certificate private key encryption. If you also have encrypted the DBM endpoint certificate with a password then you can open it using that password and then add the new master key encryption to it, afterwards the DBM will successfully connect.

If you cannot recover the original DBM endpoint certificate private key then you need to replace it. You do not have to drop the endpoint, nor the mirroring related users and certificates. You can simply create a new certificate, then associate the new certificate with the existing endpoint using ALTER ENDPOINT ... FOR DATBASE_MIRRORING (CERTIFICATE = ...). On the partner(s) (including the Witness) you need to copy the public key of the certificate, create a new certificate for it in master and have it be owned by the user associated with the previous server certificate/user/login. This is the least disruptive way.

What you did is ultimately correct, but kinda of using the sledgehammer. Given the complexity of all the steps, I don't blame you for redoing everything from scratch. See also Replacing Endpoint Certificates that are near expiration.