I just came across the Mail::Miner project by Simon Cozens out on CPAN. At first blush it seems to be addressing some of your issues -- perhaps you can join forces if you haven't already coded a solution for your problem.

Matt (how's that for a delayed response?)