I thought I'd post a follow up to this in case it helps anyone else.
The problem was with the order the services were starting on the Windows server. I still don't know what particular service was causing the problem but I guess it took a variable amount of time to start up. When it started first the FileMaker Server service started perfectly. If the FileMaker Server service got in first no databases were started.
I set the FileMaker Server service to "Delayed start" and everything has been fine since. I probably should work out the dependencies and set the services to start in the right order but at least for now it is working reliably.