Vlingo is probably the best, although I wouldn't consider it hands-free. You still have to read the screen and press buttons to save & send messages. Plus, you have to hold down the side button while talking, so it may still be condered illegal in locations that have banned non-hands-fee use.
Try MyCaption.com. You can assign a quick key to SMS dictation. Then with a single click, without even looking at the BlackBerry, simply say: "Send SMS to James, message Hello James...". Another click, and you are done.
A range of price plans are available. Judge for yourself. One man's outrageous price is another man's productivity gain, ROI, time saved, fun and convenience.