How can I decrease the time spent reformatting / restoring user's workstations?

This is imho the best answer for installing windows quickly and effortlessly:

Microsoft Windows Remote Installation Service and Windows Deployment Services

A PXE server that offers installation of windows and slipstreamed applications and drivers across a network.

The difference between the two is that WDS is newer, comes with 2k3 Server SP2 and 2k7, supports multicast and disk imaging technology.

1. Standardize the OS. 3 flavors of windows workstation? Get everyone up to Windows 7. If you're not on a Microsoft agreement of some kind, look into it. For a 150-person company you can probably justify the cost in terms of how much labor cost you'd be saving over a year.
2. Standardize the hardware. Make sure all workstation/laptop purchases from now on are Dells.
3. Get all the workstations on a domain (if they're not already) and use Group Policy as much as possible to automate the post-OS-install configuration that you perform (proxy settings etc)
4. Use folder redirection to point My Documents to the file server. Get all the users documents hosted on the network. Enable offline files with a GPO, and ensure it's business policy to save all documents into the network shares, with a clear understanding that any documents lingering on a workstation are not protected in any way.
5. Get WSUS up and running and forget about manually patching the OS whenever you reformat. Get your enterprise AV solution's automated discovery/install process working and hook it into your domain so AV installs itself.
6. Get line-of-business apps (and apps that are hard to configure) running on a Terminal Server, and make it available to the staff that need it. Give access to remote/home workers over VPN. Bask in never needing to futz around registering DLLs etc on workstations ever again.

I deliberately didn't mention build solutions (Altiris/RIS/MoM etc) because if you do all the stuff above you may find it's just not necessary for a 150-person company.

WDS comes to mind, as it is free with Windows Server and is pretty painless to configure. It will allow you to create a custom image with software pre-installed. You can also make a stand-alone solution with Windows PE and unattended answer files created with WAIK.

For paid solutions, there is Ghost, Acronis, Altaris, etc.

If you are using individual OS and software licenses though, you may be stuck, as most of these methods depend on the fact that you are using volume licensing and have the same product key for everything. This is because the custom image is captured with these keys in place, so activation may fail if you don't use MAKs.

In addition to the various server based installation/distribution methods already mentioned, which should be your first line of attack when appropriate, there is also the concept of making images of the machines on disc. It isn't always the perfect solution but when it applies it has some advantages.

In the case of PCs, which in the environments I've worked in are not always in the office or on the network, the image disc (normally a DVD) is attached to the inside of the case. This allows me to easily walk the user through a restoration even when either of us is off-site.

For laptops one copy goes to the user and one gets filed away. I find that in the case of laptops I find that the amount of work involved in removing all the crap that comes preinstalled and actually is something I don't wish to repeat. Once the machine is in a state I consider ready to use I take a new image and hide the original discs, so that the user can't use them.

Take a look at FOG, fogproject.org. It's a system based on opensource tools for cloning and restoring windows system images over a network. This won't make the handling of the profiles any easier though. Have you thought about roaming profiles for that?