tl;dr

If you receive an error “An error occurred when verifying security for the message” when connecting to Dynamics CRM, verify that the clocks on the client and the servers are no further than 5 minutes apart.

Just a bit longer

Code that was working yesterday refuses to run and spits an error on the very first message sent to CRM:
An unsecured or incorrectly secured fault was received from the other party. See the inner FaultException for the fault code and detail.
The clue is, in fact, in the inner message:
An error occurred when verifying security for the message.
Quick search reveals that I’m not the only one, and it’s been dealt with before by analyzing server logs (not available, of course, for CRM Online but on-premises it’s a good option). Step by step troubleshooting instructions are in the knowledge base article that deals with Outlook connectivity issues (the root cause is the same).

Worth noting that the lines:

CrmConnection con = new CrmConnection("connstring");
OrganizationService svc = new OrganizationService(con);

do not mean “connecting to CRM”. Connection will not be authenticated until the first use. That’s why, where applicable, I tend to write:

CrmConnection con = new CrmConnection("connstring");
OrganizationService svc = new OrganizationService(con);
svc.Execute<WhoAmIResponse>(new WhoAmIRequest());

that way, if it fails, it’ll be very early in the execution.