Recently a few of the folks I work with that use Macs noticed Entourage 2008 was having trouble using Exchange 2007 Web Services properly (as it advertised it would). I tried it out from home and verified the same thing, that the Out of Office Assistant and Free/Busy lookups didn't go so well. I've been meaning to get around to building an OS X 10.5 virtual machine so I could hook it into my VM environment and do a packet trace to see what was going on, but it seems like I won't need to anymore. Just update your friggin' client to SP1 and EWS works properly. They've also added support for Autodiscover. I haven't had a chance to play yet, but I wonder what kind of lookups and certificate restrictions Entourage has compared to Outlook.
So, moral of the post - problems with Entourage 2008 for Mac and you've got an Exchange 2007 environment? Upgrade your clients to SP1.