Something I discovered today while playing with Visual Studio 2008 and new book Inside Microsoft® Exchange Server 2007 Web Services.
When I was following the guide (which is for 2005/2003) it said add a web reference. I couldn't see web reference so I (stupidly) assumed Service reference was what it meant. It turns out on the Add Service Reference page there is an advanced button at the bottom. Click that, then click Add Web Reference.
Might save you a headache or two.