Although polling a webservice is possible, do you know of another method to push changes to a mobile client except using the exchange server mail transport?
As Mark Seemann worte: I once did a POC of a client notification system for .NET CF when I was in the Microsoft Dynamics Mobile team.
At the time I didn't find any Out-Of-The-Box solutions that could do this and I didn't want to piggyback on the Exchange Server connection since the intended users didn't have a AD account and most certanly didn't use the exchange server. So I was in the same situation as you are now. I started searching for possible solutions...
I realised that the server coudn't connect to the client since the IP address of this constantly changes (going from 3G to WiFi, loosing connection, etc). The clinent had to connect to the server. Furthermore I found that most networks allows HTTP connections but not always custom TCP connections over custom ports.
I used "Comet" to do long-held http requests from client (.NET CF) to server (IIS) and pushed the notifications to the client using this connection. If the client got a timeout before a notification was given it would simply make a new request.
On the serverside I used a combnation of an AsyncHttpHandler and wait threads that checked for messages to the connected clients every sec. It is important to use a AsyncHttpHandler or you'll block the IIS server.
The POC worked well and it proved to be a reliable solution. There are some drawbacks to this: if you are not careful you'll drain the battery quite quickly.
Unfortunately there are simply too many lines of code involved for me to post the code here, but if you like you are more that welcome to contact me and I'll e-mail you my POC.