Anyone have suggestions what can that be?
Not what you want to hear, but it could be almost anything. At the moment, all you really know is the service is sometimes taking too long to either startup or shutdown.
You really need to go back to whoever developed the .Net services to see if they can help you diagnose the issue.
But before that I would recommend that, instead of using restart, you try stopping and starting the service as two distinct actions (with a short delay between them). This may help determine if the problem is when shutting down the service or when starting back up. They might also find it useful if you can determine how long a successful start and stop take.
You should also check the event log to see if any other information is recorded.
When a service starts, the initial startup phase is supposed to be complete within a specific time (normally 30 seconds). Hence a service would normally try to keep the amount of code in this section to a minimum and starts a background thread to perform the rest of the work.
Similarly when you stop a service, it is supposed to complete that process within a specific time (normally 20 seconds). This means that any long running operation should be written in such a way that it can be cancelled if the service is being shutdown, rather than waiting until the operation has completed.
Anything that causes the total startup or shutdown period to exceed the limit will cause the error you are seeing.
To give you a few examples that could cause the error.
Suppose on startup, your service is performing a DNS lookup for a computer/server name. This would normally take milliseconds, but if the DNS is incorrectly configured on the server, this could take 15 seconds or more to complete, which maybe enough to take the total time to startup over the limit. The second attempt may have the DNS entry cached and hence work within the proper time limit.
Another possibility is that the service is relying on a device or resource that has gone to sleep and the time it takes to wake it up is taking it over the limit. When you try the service the second time, the device has already awake and responds in a timely manner.
If the .Net services are widely used, you might get lucky and find that someone else on the internet has had a similar problem and has found a solution. But the actual cause depends very much on what the service is actually doing when you startup and shutdown, which is why you would be better talking to the developers.