User Interface Privilege Isolation (UIPI):
Microsoft Windows Vista and later.
Message sending is subject to User
Interface Privilege Isolation (UIPI).
The thread of a process can send
messages only to message queues of
threads in processes of lesser or
equal integrity level.
Source
You can read about User Interface Privilege Isolation (UIPI) here.
To get around this you can set uiAccess to true in your manifest file. You also have to make sure your application is signed using authenticode with a certificate from a signing authority such as verisign. This can get pretty expensive.
Session 0 isolation:
It is also my belief that you can't call SendMessage across sessions. So if you have a service running in session 0 you need to find another means to communicate with your process that would be running in a session > 0. Example: via pipe.
In Windows Vista, Windows 2008 Server and later all services run in session 0, and all applications that you start run in session > 0. This is called session 0 isolation. Here is a good document that has information all about session 0 isolation.
If you don't have access to the source of the program you want to send messages to, you could get around this by making an application that communicates with your service and acts as a proxy to relay the message to the application in its same session.
Ovearll:
If you develop your application on pre-Vista and it works fine. There is a very high chance it will be broken in Vista.