We're still running Domino Server 6.5 and using Notes R5 client on our domain for political reasons. Given how wonderful Notes is, the IT Office staff uses Outlook 2003 with the Lotus Notes Data Connector (available from MS for free). It works great, and means we don't have to use Lotus Notes in the office.
Recently we found that users who were setting up new Outlook Profiles using the Notes Connector were having issues with Outlook spitting out a "Unable to open your default email folders. The server is not available. Contact your administrator if this condition persists." error when the user tried to use their new Outlook profile. Looking at the Outlook log files it was showing "Error in CABProvider::QueryInterface failed, E_NOINTERFACE (0x80004002)". The odd thing was that anyone who had an Outlook profile that had already been setup and used for awhile was not having this issue, even on the same machine.
So after doing some research it turns out that some of the latest hot fixes for Office 2003 SP2 break the Notes Connector (only the olconn2.exe , which hasn't been updated since 2004). Specifically they are KB916521 , KB892843, and KB913807. There may be a couple of other roll-up hotfixes that break it, but these are the latest once I could track down. The kicker is that you can't just remove these hotfixes, you actually have to uninstall Office 2003 SP2 and the Notes Connector. You then have to reinstall both, making sure to disable Office Update from installing these hotfixes until after you have created the profile. Strangely, the older Notes Connector (olconn.exe) has been recently updated on 5/9/2006 and apparently works with all of the latest hotfixes (albeit only for Outlook 2002).