A Volume Shadow Copy Service operation failed. Detailed error: The volume shadow copy operation failed with error code 0x800423f0

Windows Small Business Server 2011 randomly started to fail backups.

Backup console shows the following error:
A Volume Shadow Copy Service operation failed. Detailed error: The volume shadow copy operation failed with error code 0x800423f0

First things first, run a "vssadmin list writers" from a elevated command prompt. Output shows this to the be the faulty writer:

Writer name: 'SPSearch4 VSS Writer'
Writer Id: {35500004-0201-0000-0000-000000000000}
Writer Instance Id: {2f53b890-9998-4a18-8859-a5b70b3a56a3}
State: [8] Failed
Last error: Inconsistent shadow copy

This is usually a sign that Sharepoint needs updating (guide here) but upon running the "(get-spserver $env:computername).NeedsUpgrade" in the sharepoint shell I relieve:

(get-spserver $env:computername).NeedsUpgrade 

False

OK, not a sharepoint upgrade then! 

I check the services - all are running. For good measure I restart all the sharepoint services one at a time:

SharePoint 2010 Administration
SharePoint 2010 Timer
SharePoint 2010 Tracing
SharePoint 2010 VSS Writer (this is probably the only one that needed restarting)
SharePoint Foundation Search V4

I also restart the sharepoint SQL service
SQL Server (SHAREPOINT)

Re-run the backup job and voila - working.

A server reboot would probably have done the same.. but my clients don't like reboots during working hours