First of all id say if you have mailboxes that big it cant all be work data, make sure you have file name filters for mp3, wma, ogg, wmv, avi, mpe, mpg etc etc
Secondly fire up exmerge and do a 'copy' extract of any mails with those attachement filenames, you dont have to view the content (i.e. possible invasion of privacy) but you can look at the pst file sizes to determine if those mailboxes contained such files. If you definately have a problem and a big space saving you can speak to your management about introducing a ban on those files and then rerun exmerge as a move into psts, backup the psts (just in case) then delete them
Symantec Evault is a good option even if i dont like the software too much, it introduces the idea of tiered storage i.e. if your exchange servers disks are high cost/high activity then you dont really want to be keeping data in them that is used infrequently and its vaulting policies cater to that, you can also switch vault stores periodically so that existing stores become frozen and you can then back them up less frequently because they wont have new data flowing into them.
If i remember rightly its also licensed on a per user basis, you can install with a limited number of licenses and only enable it for your worst offenders
There are other solutions like ways of automacally dumping attachments to folders but its messy and you loose single instance which doesnt happen if you stick with exchange/evault
Ofc course this is all bad advice since the best solution is exchange 2010
