Suggestions Please: Active Directory Stucture, Group Policy Management

For Computers:
I would make a sub-OU (folder) under Workstations for each branch as well as one for Coroporate Office, then get specific with the machines inside that. Such as sub-OU's for Management, Accounting, HR, etc. If you have multiple uses of machines, then make more sub-OU's under Management, Accounting, etc, such as Laptops and Desktops. If Accounting has different sub-departments, create them under Desktops. Granularity in your OU structure helps tremendously when distributing group policies. You may want to create a policy to push a program only to Accounting's desktops. Or a policy to push a registry setting to just laptops. Here's an example of a good OU:

Workstations
- Branch1
   - Accounting
      - Desktops
         - Others
         - Phone Sales
         - Website Sales
      - Laptops
   - HR
      - Desktops
      - Laptops
   - Management
      - Desktops
      - Laptops

*repeat for Corporate Office OU and other branches so your main AD tree would look like
Workstations
-Branch1
-Branch2
-Branch3
-Branch4
-Corporate Office

For Users:
Use the same logic as above. Start with the Branches, then the Departments, then maybe additional sub-OU's for sub-departments or type of job.

Users
- Branch1
   - Accounting
      - Managers
      - Other Staff
   - HR
      - Managers
      - Other Staff
   - Management
      - The Big Boss

As a network admin, you definately WANT your machines joined to the domain. It allows you to see what you have out there and better secure your machines. Group policies won't work on non-joined computers, and policies are the lifeblood of a corporate network. Also, it will be more tedious for you to remotely manage those machines. Tasks such as changing the local administrator password every so often or installing new programs/updates would become a manual chore, rather than a scripted breeze. I could write several pages of reasons for joining machines to your domain, but none for keeping them off it.

Have a local user account on the laptop for when they're elsewhere, and when on your network, they can login to the domain controller. It's a matter of choosing the location on the login box, either YOURDOMAIN or "COMPUTERNAME (this computer)". If it's a personal laptop (which some business flat-out refuse to support, just one of your options!), they can still login with a local account and access your domain resources, if they don't mind being prompted for an authentication box everytime they do something.