Queue file size limit exceeded in Postfix

I encountered this error today in our Postfix based mail archive server (mailarchiva). We use it to archive email from Google Apps and route our email through it.

We received complaints of people not being able to send attachments, getting an error message similar to:

Delivery to the following recipient failed permanently:

Technical details of permanent failure: