Think a possible cause has been found. Overnight a MAXDOP from 1-to-4 runs, and a bit later it then sets things back from 4-to-1 - it looks like the cache flush that should happen as part of that is unreliable. Manually running a DBCC FREEPROCCACHE afterwards is needed. I suspect SQL Server is somehow retaining a footprint from the MAXDOP 4 setting while it the compiles the query plans.

This would explain why a failover fixed the issue, as it forced the cache flush.

Fingers crossed that has got to the bottom of it.