There are a lot of things in the iPhone SDK that should be easy to do but they are not, and this is one of them. Changing the Mail Compose View Controller title should be as easy as:

[myMailComposerVC setTitle:@"My title"]

but if you do that you don’t get anything, you still get the “NEW MESSAGE” text.
The way I found to access it is the following. Maybe there is another/better don’t know but this one definitely works:

[[[[myMailComposerVC navigationBar] items] objectAtIndex:0] setTitle:@”My title”];

Hope it helps someone as much as it helped me.