Windows and Exchange will certainly be able to use multiple cores, but a 25-user network isn't a big load on an Exchange server. (An Exchange server is a huge load on an administrator, or on a person who wants email to work properly, but that's another story.)
I currently run an Exchange (2003) server at a remote office with 35-ish people on a single Xeon 5160 (3GHz, dual-core) with 4GB RAM, and I've never had any load problems, and it is also an AD, DHCP, and DNS server.
When you say the remote offices connect via Citrix, will your Exchange server also be the Citrix server, because that will have a significant impact.
_________________________
Bitt Faulk