Check on Cisco's website for the recommended Exchange SP's for your version of Unity. Do not use Microsoft's unless Cisco says it's OK. Here's a brief sample from Cisco.com:
Exchange 2000 Service Pack 3 for Cisco Unity 4.0(4), whether you are installing Exchange 2000 on the Cisco Unity server or connecting to Exchange 2000 on another server.
Service Pack 3 is also recommended for Cisco Unity versions 4.0(1) through 4.0(3). Service Pack 2, which is the required service pack for Cisco Unity versions 4.0(1) through 4.0(3), is still supported for those versions but is not recommended.