I know this was dead -- but I figured, since I just found the answer, and this un-answered thread at the same time (I had the same question and used google), I might as well go ahead and answer it, in case anyone else is ever looking for the answer here.
In the main view press "D" (Shift + d)
At the bottom it asks "Delete messages matching:"
Enter the following and press enter.
All messages will be marked for deletion. Now just press "q" to quit and "y" to confirm you want to delete all those messages.
(The ~s makes it search the subject for the given expression and of course ".*" is a global regex wild card.
See this page for more details. http://www.mutt.org/doc/manual/manual-4.html)