"Corrupted key" error when creating/updating SQL Server 2012 credential for proxy account
I am going to attempt to answer my own question (as my experience may help others). Firstly, regarding the issue I experienced, I found this blog helpful (as were the comments from Sean Gallardy above).

As I had no Service Master Key (SMK) backup to restore from, my intention was to regenerate a new SMK using the ALTER SERVICE MASTER KEY REGENERATE with the FORCE option (causing loss of encrypted entities). I was prepared to have to recreate my credential secrets and Linked Server passwords. This instance had no Database Master Keys but, had it done so, I could have opened them using their password and regenerated them by the SMK (thus avoiding data loss).

However, I decided first to see if a simple restart of the SQL Server instance would resolve the issue - and it did! Upon restart, the Service Master Key verified successfully (and I confirmed this by creating a new test credential successfully).

My best guess is that whatever issue prevented the SMK verification previously (causing the "Service Master Key could not be decrypted using one of its encryptions" error log entry) had disappeared. I know that the SMK always has two encryptions: the machine key encryption and the service account encryption (and these provide an either-or decryption method in the case of cluster failover or service account change). 

As the host WINTEL server was having issues, I imagine that invalidated the machine key encryption. I can't imagine what might have been invalidating the service account encryption (that account did not change) but whatever it was, it seemed to be a temporary problem. So my best guess is that, upon restart, the SMK was able to self-verify using the service account encryption (and, at that point, create a new machine key encryption).