My office migrated from using Outlook/Exchange to Lotus Notes/Domino recently (corporate orders, we loved Outlook :-) and as you are reading this I'm pretty sure you think too that Lotus Notes 6.5 can hardly compete as an email client with Outlook 2003, surprisingly though both of them were released about the same time.
If you found the Outlook Lotus Notes Connector doesn't work for you, then it's very likely that is due to the fixes that have been released since 2004, see the post below documenting on how to make this work.
In my case, I couldn't uninstall all fixes so I had to uninstall Office 2003 completely, install it fresh no fixes/service packs, then the Lotus Notes Connector and then the SP3. It works a treat, we'll see how it goes. Definitely read carefully the connector's Readme.htm it shows during the installation, just to be aware of certain problems.