This may depend on the scope of your project. Stilleto's proposal of copying the database and deleting the unwanted messages is good. It's also very easy to copy and paste documents from one database to another.
For option 1 (Stiletto's), you would select File, Database, New Copy, and then start deleting from the new database. For option 2, you create your new mail database (File, Database, New; or CTRL-N), select the Notes Mail template. Then go to the original db, select a folder, select all documents in the folder (CTRL-A), copy them (CTRL-C), then go to your new db, create folders if you need them, and paste them in (CTRL-V).
You say there are tons of folders. If the particular messages can be identified by a search query, for example, if you're looking for a particular sender, that could be much easier than going through every folder. Run the query on the All Documents view.