If you aren't using the WSE 2.0 stuff yet then I would recommend walking through this article:
Web Service Messaging with Web Services Enhancements 2.0
I hadn't explored the WSE stuff until I read this article which provides a nice walkthrough if you code along. My only complaint is that after you add the Reply-To messaging it won't work until you add the config settings. I hadn't scrolled down to the config part and was very confused as to why my subscriber wasn't getting the subscription response message (although maybe this is a good lesson to learn).
Another issue I ran into was the code used to call the web service proxy generated by VS. It seemed to be referencing some of the older code in the article versus where the example is placed. However, it was very easy to figure out the correct code for once I got there.
Overall a great article and well worth the read.