Telstra HTC Velocity 4G Rocks
I know it's a bit late for the OP but I wouldn't mind sharing my opinion anyway.
I migrated from a rooted HTC HD2 with a custom rom and agonised for ages between the HTC Velocity 4G and the Samsung Galaxy S2 4G.
I was able to test these units side by side at a Telstra shop in Adelaide recently to help me decide, the first thing I noted was the speed of the HTC Velocity compared to the SGS2.
Both phones were loaded with the speedtest.net app and were set to the same server, the HTC Velocity consistently had ping times to the server of 91ms where the best time for the SGS2 were 281ms. Download speeds for the Velocity were better than 27Mbps where the SGS2 couldn't get over 17Mbps, now that is a big difference!
The screen colours on the SGS2 were too saturated and dark and didn't seem real.
All in all the HTC Velocity 4G is awesome in my book, my wife has an SGS2 and I still hate the way it does some stuff and just doesn't seem as user friendly or as configurable as the HTC Velocity.
Hope this helps someone.