Can some JavaScript be added to the Create Message code, so that if Subject is left blank, instead of putting 'untitled', the user is prompted to enter in a subject line?
Some browsers may not run the JavaScript, but with luck most will and the prompt will be enough to get people to title message threads they start.