I just used a numeric code for each store. there is a 9 prefix for one, 8 for another resulting in 9000001 etc. If you have over 8,999,999 orders in a short amount of time (averaging 24658 orders a day in a year), I would think you might want to pay for some serious programmer to build your own place (by that time, you sure as hell should be able to afford it!)
Just a blonde suggestion.
Ana