After many tries, I finally found out how to get Mail.app to open a new message window using AppleScript:
tell application "Mail"
set t to make new outgoing message
set visible of t to true
activate
end tell
Save this as an AppleScript using AppleScript Editor, and then tie a keyboard shortcut to that script using your favorite keyboard shortcut creation tool. Tested with 10.6.1.
[robg adds: This also works in 10.5, and probably many releases before that. Spark is one of many program you can use to create the keyboard shortcut. In 10.6, you could also create this as a Service using Automator, and assign a keyboard shortcut in the Keyboard Shortcut's System Preferences panel.]

