Lenny- if your're still looking, check out Vertias Netbackup Puredisk Remote Office Edition (needs a longer name- let's add "by Symantec"
)
We are beginning to switch over, and so far I'm pretty pleased. I ran a job from each system on the same server last night- took 1 hour 44 min on RE, 1 min 28 sec on Puredisk. It has better reporting IMHO, and de-dupes your data at the block level. I'm seeing between 20% and 60 % reductions in data right out of the gate.
Licensing is by the TB, so you might find it price-competitive if you have lots of small sites.
No one at VeriSymantec is saying this that I know of, but I personally believe that RE is on the way out. I don't see much movement in terms of features or enhancements- just patches for the last 18 months.