I don't use any custom templates in my store; just the stock Top Notch template.
I'm on a Verio VPS Solaris Pro:
http://verio.com/vps-solaris-pro/
As such, I don't really have much insight into the actual load on the server...
I ran another test regen / reindex on my two stores (mirrors / sisters of each other; identical except for item prices; sync'd with the Shopsite sync utility), both of which are on this server:
Store 1:
top CPU time: 2:45
real-world time: just over 9 minutes
Store 2 :
top CPU time: 4:40
real-world time: 16 minutes
In both cases, generate.cgi was ranging from around 3% to 40%usage in
top
One thing I did notice during the publish - the item numbers in store 2 are getting REALLY high - over 9,000 (even though the number of actual products is around 1500. Could this be an issue with the sync module / database which is slowing things down?