Man, this sounds like on of the questions out of the MCSE AD design exam.
First, assuming that you are choosing the single-forest, multiple domain model, and assuming that you want the head ofice to be the root of the corporate AD forest, you definitely want to start with the head office.
Second, if at all possible, cut down on the number of domains. This is easiest if you have any locations that have separate account and resource domains.
Any trust relationships currently in place between domains will be maintained (NOTE: Trust relationships between AD domains in the the same forest are automatic, two-way, transitive trusts. Trusts between an AD domain and a non-AD domain are configured manually, and are non-transitive.). If trust relationships don't exist, at the very least, you will need to setup one way trusts between the forest root domain and the child domain to be migrated to AD.
Exchange 2000 must be installed in an AD domain on a Win2K server (although the server doesn't have to be a domain controller). If you are planning on a single Exchange server for the entire organization (as opposed to an Exchange server in each domain), your best bet would be to wait until your entire organization has been mograted.(NOTE: if you currently have EXchange 5.5 installed, it will continue to work well in your AD domain. If you do have Exchange 5.5 running, I would consider doing the migration to Exchang 2000 as a completely different roll-out as opposed to tryingto do it at the same time as the Win2K roll-out.)
Hope this helps.