It is not much that you can do, but there is a hope.
You can just switch to T-Mobile, they advertise unlimited blackberry inbox. Put them to test.
You can try Email Reconcilliation.
Open Options, Email Reconcilliation, select the following:
Message Services Web CLient
Delete On: Mailbox & Handheld
Wireless Reconcile: On
On Conflicts: Handheld Wins
When you receive email with large attachment, delete that email. Do not use Delete Prior, you must delete emails one by one.
That should remove deleted messages from BIS account. If you want it faster, after deletion open Options and select Reconcile Now.
It is assuming that feature works as advertised and available on your blackberry- that depends on blackberry software version.
Really, for you it will be much easier just switch to T-Mobile.