I found this interesting post on the kde-pim mailing list which is very to-the-point and informative on how to connect KMail to Exchange. You do need IMAP enabled on the Exchange server but once you get over that hurdle - and believe me, in a pure Microsoft shop it's a big hurdle - you're good to go.
I haven't gotten Calendar integration working just yet but I haven't put a lot of time into it yet. This page on the KDE Wiki explains how to use webdav to perform one-way syncs against an Exchange server using a plugin for KOrganizer.
Edit: Even brought it to my attention that the KDE Wiki link is no longer working. It seems the KDE wiki has changed structure since I was last on it. I found Jason Kasper's blog, however, where he's talking about a ruby-based solution to the 1-way sync between an Exchange OWA server and KOrganizer.