I applaude you for making this effort. I wish more companies would! Getting into a 3-4 year rotation cycle will save you a ton of cash and that makes the powers that be rather happy.
Here are a couple of things to consider...
1. Thin Client and Terminal services or Citrix MetaFrame.
This offers a way to hold on to the older systems and not have to have a new PC at every location. Thin Client devices are C H E A P and easy to maintain, no OS loads, no software loads, no patching etc.. if the hardware fails, you pull the device and put a new one in it's place.
A TS and or MetaFrame environment offers killer TCO and ROI when compaired to new PC class devices. Also there is centralized management and just a ton of other wiz bang features that make life easy for your helpdesk/sys admins and desktop folks.
2. Product life cycle and road maps
Pull your vendors in and insist on a product road map. Look at the life span of the whole system. Are they going to change Motherboards or other components on you within 12 months? If so it isn't worth purchasing that system because your image management will drive your people INSANE! Not to mention it takes you right back to where you are with the exception of the name or color of the PC.
3. Be prepared to hagle! My favorite is something like this... Look, I'm going to replace 600+ systems over the next three years, call it 200 systems +/- per year, I want to average the total price of the system for 12 months and pay that average from the start.
This approach works. If you can forcast your purchasing that makes the life of the reseller Super easy.
4. Consider your VAR closely. Make them compete for the job. Don't rape them on the numbers, they have to earn a living too, but it is very realistic to have 3 or mor VAR's compete.
Beware of the Dell and Gateway black holes... Dell could care less (or so it appears to me) about the small medium businesses of America. Gateway, well they're getting better but they still have the same bacic issue as Dell. If you want a vendor that can really take care of you, CDW is the Vendor by which I judge all others! They treate the Small Business as good as they treat the big ones.
Just realize that you are going to commit yourself to a manufacturer and more than likely a model line for 3+ years.
Also realize that if you manage it, a Lease is a good way to go and it lets you recycle your environment on a fairly set time frame. It does take good record keeping and asset management, but personally it is the way I like to pay for this type of effort.
Good Luck