I have added the velocity master variables replacer to the extended mail action, and put them together into one project and package.
Thanks to Jakob, adding master variables replacer is as easy as it gets now, just put your class into
<setting name="MasterVariablesReplacer" value="Sitecore.Data.MasterVariablesReplacer,Sitecore.Kernel.dll" />
in web.config and derive from default Sitecore.Data.MasterVariablesReplacer. No need to hook in the pipelines!

VelocityMasterReplacer works much like the Extended mail action. Instead of having only a few predefined macro expansions like $name and $parentName, you can now use pretty much anything accessible via the Sitecore API: $user.Name, $item.Children.Count, $item.Paths.Path, $item.Fields["Text"] and even the flow control:
#foreach($child in $item.Children)
   Child - $child.Name
#end
(Make sure that you know this before trying that trick with children)

It is also backwards compatible - after the velocity replacer does its job, it calls the base method to finish the rest.
Anyway, here's the source files - SitecoreVelocity_1.1.0.0.zip (411.82 KB). (You will need Sitecore 5.1.0.4 aka 5.1 beta1 for that)

If you just need a package - its in the /data/packages folder of the archive.

Update: sorry, link fixed.