(1) NT 4.0 w/a Service Pack pre-6a has a bug: TCP/IP can prematurely retransmit packets to clients over slow connections, dramatically degrading throughput.
(2) The drive with the Information Stores shouldn't be shared with anything else. Exchangeintegrity is maintained by a structure of transaction logs and database structure files which are constantly reindexed during normal daily email usage.
(3) With a matrix of interlinked files like above, there's a greater possibility of file/data corruption. Also, while Exchange runs on-line defrags of the Stores throughout the day, it cleans the holes in them but doesn't decrease the filesize. EDBUtil is one of a few performance & optimization tools that come with Exchnage. Run it against your databases looking for corruption, but be careful to only use the switches to check them first. Microsoft suggests that running the 'repair' or 'optimize' options when the databases don't need it, can damage them.
(4) With that many remote locations, I recommend that you implement maintain more than one server. Even just an additional 1 or 2 serving as hubs would improve performance.
(5) Regardless of above, if you're still maintaining Personal Address Books (.pab's), store them local to their owners. The less going across the wire the better.
(6) Exchange server-client & site-to-site communications are handled by Remote Procedure Calls (RPC). So are other Microsoft app's communications. RPC creates an Open (something-or-other) link between servers (view in Server Manager). I don't know about Win 2000, but in NT 4.0, (a) These links don't always close and (b) only a max. of 40 links can be maintained
See Microsoft site "Exchange Resource Guide" for more optimization tasks.
Of course...it could be the circuit.... ;>)