Couple of possibilities here:
1. You don't have to move Exchange to a new server to get more space. Install a new hard drive on your present server. Then use the Exchange Performance Optimizer to move your information stores and log files to the larger hard drive. This would be by far the easiest and least expensive solution to your problem.
2. If you are set on moving Exchange to a new server, don't try to do everything (migrate mailboxes to new server at the same time as you migrate to a new version) at once.
3. You don't need Advanced Server if you on't plan on taking advantage of it's increased capabilites over Server (clustering, more processors).
4. To move to a new server, here is the process I would suggest: Install Exchange 5.5 on the new server as an additional server in the smae site; migrate all settings to the new server; upgrade new server to Exchange 2000.
Good Luck.