Yes, all are nice ideas, I've had some of them in mind myself (I've even implemented the PM search into the Search Page Upgrade mod).
But I'd say it would be better to scrap the Messages table completely and use the normal Posts table for PM:s as well. No need to reinvent the wheel. If the normal functions are used we will get all the functions from the posting pages (we still haven't got the signature in PM:s, or the Quote feature). We will also get search possibilities, better browsing etc. There would also be easy to follow discussions in PM:s because they are threaded (or, could be shown in flat mode as well).
I'm not sure exactly how to implement this, but I guess there would either have to be an external table connecting users to threads in a special hidden "PM forum". Or possibly an extra field containing the user numbers of the users allowed to read the thread. I'd prefer the first option, since it's more scalable and is a better database structure.
Of course, there would have to be some checks in the search page so that it won't be possible to see PM threads that the user isn't allowed to read. Could possibly be done with an option to search in either posts or PM:s.
The idea with folders and filters is nice as well, but I would say it's the least important feature.
PM ignore feature is a definite must.
