As TBN says, just check the boxes, choose delete from the menu at the bottom, and hit go. If you want to keep things, put them into your saved items folder, or export them.
As noby says (this is a recurring theme, as it was the same with the old version) messages stay in your outbox until the recipient reads them. So basically, you're being ignored <!-- s:D --><img src="{SMILIES_PATH}/icon_biggrin.gif" alt="

" title="Very Happy" /><!-- s:D --> I've one message in mine for months!
@noby, I think you're right, it'll push the old messages out if a new one comes in and you're over the limit (currently set to 60).
Actually, I think the messaging is a lot better then the old phpBB version.