There are heaps of phones that can sync with Outlook but if you're going to be doing a lot of swapping of appointments and adding details on the device, think about what type of input system you'll need -- such as a QWERTY keypad to type fast messages or a touchscreen to drag and drop appointments.
Some options we'd suggest looking into:
All of the Nokia 6000 series phones come with PC Suite (Nokia's synchronisation software).
The Dopod 838 Pro is a popular (but relatively expensive) model, too.