If it happens at roughly the same time and only on the first Wednesday of a month, then there's something scheduled or a human is running something at the same time or....

Since bouncing the service works, it could be a parameter sniffing problem (bouncing the service certainly clears cache) cause by someone running a month-end job or something similar. My first shot in the dark on this would be to add a forced RECOMPILE to the proc.