Na das ist ja nicht so schlimm, das schafft ihr locker. Wie gesagt, mit Domino kannst du beschränken, oder große Mails auch zeitverzögert zustellen. Vielleicht solltet ihr auch über Archivierung nachdenken?
Mit iQSuite kannst mehr auch machen, sind recht gut. Oder, wennnn ihr z.B. Trendmicro Scan Mail verwendet, die können auch Mailbeschränkungen. Es gibt genug Lösungsansätze.
//edit: achja, ab V6 kann Notes DBen bis 64 GB verwalten, da habt ihr ja noch Zeit ;-)