Send windows message to a Windows Service

If you have the hwnd of a window you can send it messages. The only limitation is that you can't send messages that contain pointers like setting window text.
Simply call PostMessage() with the value of the hwnd and the message you want to send.
To find the hwnd you can use spy++.

I'm not sure how you connect all this to windows services since windows services don't have windows.

Check out the answers to How to simulate windows shutdown while debugging?

Services have an 'event' called OnShutdown they can subscribe to, so it could be the problem is in that code. If the code is .net you could subclass it so you can call the protected OnShutdown method to debug. But the problem could also be as suggested by others that the service is expecting resources to be available which aren't because they've already been closed.

Also, if the service was written in .net 2.0 note that the Stop() command isn't called automatically on a service when the workstation is being shut down! This is very surprising and was fixed in .net 3.5, but if you're using .net 2.0 you need to call Stop() yourself within OnShutdown().

Services should be controlled using ServiceController class

Represents a Windows service and allows you to connect to a running or stopped service, manipulate it, or get information about it.

You can use it to start, stop and communicate with services using this class.

Generally, services don't have windows (let alone message pumps) to receive a windows message.

If the bug really does only happen on shutdown (as opposed to just stopping the service), it may be the case that something depends on a resource that is going away, which is not being handled gracefully (in which case, the bug fix might be to set up the service dependencies correctly). Have you tried using the remote debugging tools to attach to the process prior to shutdown?

It's worth investigating if you can get the problem to occur without shutting down, perhaps when just stopping the service with the Service Control Manager (no need to do this programmatically, as this is a debugging scenario), in which case, you can breakpoint OnStop() in your service (I'm assuming C#) and watch what happens.