I haven't used Outlook Business Contact Manager, but it probably uses a version of the "Microsoft SQL Server". This being Microsoft, I wouldn't expect the product to work with any other brand of SQL database.
Personally, I would suggest either looking for an Open Source (or at least Linux friendly) application, or accept the requirements for whatever Windows-based app you choose. If you are prepared to live without Outlook integration, then there is likely to be a Web application that will provide you with addressbook/CRM functionality. Groupware apps like eGroupware or the Horde are most likely to have modules for this kind of thing.
I'd also suggest doing at least one trial-run on a virtual machine (VMware player image) or test machine, and using that test system for a couple of days. Document the steps that you took to get it all working and configured to your satisfaction. You can then confidently reproduce the steps on the live system and even copy databases, config files etc. across to speed up the process.
FWIW, you only ever need to down a Linux box to upgrade the kernel - you can happily install and configure a bunch of new software whilst the existing services tick along. Although it's best to schedule downtime, if only to ensure that people don't distract you whilst you are working
.