I immediately updated all our Umbraco sites after receiving the following security bulletin: http://umbraco.com/39310. The patch worked fine on all 4.5.2 - 6.2.4 installations, but we were seeing a sh*tload of errors (see below) in the Umbraco log of a 7.1.6 installation hosted on Azure. And according to the client published changes were randomly rolled back by Umbraco. So we were forced to undo the security patch. Help would be much appreciated.

All these nodes were in fact published (and visible on the website), so I have no idea where the following errors were coming from:

2015-02-07 04:44:17,248 [7] WARN  Umbraco.Web.Routing.DefaultUrlProvider - [Thread 11] Couldn't find any page with nodeId=10019. This is most likely caused by the page not being published.
2015-02-07 04:44:17,248 [7] WARN  Umbraco.Web.Routing.DefaultUrlProvider - [Thread 11] Couldn't find any page with nodeId=9996. This is most likely caused by the page not being published.
2015-02-07 04:44:17,248 [7] WARN  Umbraco.Web.Routing.DefaultUrlProvider - [Thread 11] Couldn't find any page with nodeId=9997. This is most likely caused by the page not being published.
2015-02-07 04:44:17,248 [7] WARN  Umbraco.Web.Routing.DefaultUrlProvider - [Thread 11] Couldn't find any page with nodeId=9994. This is most likely caused by the page not being published.
2015-02-07 04:44:17,248 [7] WARN  Umbraco.Web.Routing.DefaultUrlProvider - [Thread 11] Couldn't find any page with nodeId=6694. This is most likely caused by the page not being published.

We were also seeing a lot of scheduled task related errors:

2015-02-08 21:41:21,200 [8] ERROR Umbraco.Web.Scheduling.ScheduledPublishing - [Thread 24] An error occurred with the scheduled publishing
System.Net.WebException: The remote server returned an error: (400) Bad Request.
   at System.Net.WebClient.UploadDataInternal(Uri address, String method, Byte[] data, WebRequest& request)
   at System.Net.WebClient.UploadString(Uri address, String method, String data)
   at System.Net.WebClient.UploadString(String address, String data)
   at Umbraco.Web.Scheduling.ScheduledPublishing.Start(ApplicationContext appContext)

And:

2015-02-09 20:22:57,791 [9] ERROR Umbraco.Web.Scheduling.ScheduledPublishing - [Thread 22] An error occurred with the scheduled publishing
System.Net.WebException: The remote server returned an error: (404) Not Found.
   at System.Net.WebClient.UploadDataInternal(Uri address, String method, Byte[] data, WebRequest& request)
   at System.Net.WebClient.UploadString(Uri address, String method, String data)
   at System.Net.WebClient.UploadString(String address, String data)
   at Umbraco.Web.Scheduling.ScheduledPublishing.Start(ApplicationContext appContext)

And finally these errors:

2015-02-05 14:29:19,564 [7] ERROR Umbraco.Web.Mvc.AdminTokenAuthorizeAttribute - [Thread 9] Failed to format passed in token value
System.Security.Cryptography.CryptographicException: Error occurred during a cryptographic operation.
   at System.Web.Security.Cryptography.HomogenizingCryptoServiceWrapper.HomogenizeErrors(Func`2 func, Byte[] input)
   at System.Web.Security.Cryptography.HomogenizingCryptoServiceWrapper.Unprotect(Byte[] protectedData)
   at System.Web.Security.FormsAuthentication.Decrypt(String encryptedTicket)
   at Umbraco.Core.StringExtensions.DecryptWithMachineKey(String value)
   at Umbraco.Web.Mvc.AdminTokenAuthorizeAttribute.AuthorizeCore(HttpContextBase httpContext)