I tried IMAPSize as well, but it is no longer supported, crashed sometimes, and left behind messages that it seems it should have deleted. There is also the Unattach app for GMail users, though I can't vouch for it.
To solve it for myself, I made a python script that may be of use: IMAP Size Reducer
It works on one specified folder per run. As long as you know how to run python scripts on the command line, how to log in to your server (URL, username, password), and the IMAP folder specification (e.g. "INBOX.Sent"), it should work with any IMAP folder. (Your ISP can help with those details if necessary.)
You can specify the "max desired message size" (i.e. "if the message is larger than this size, remove attachments until it is under this size") and "tolerable part size" (i.e. "if an individual message part is under this size, don't delete it, no matter the overall message size").
The following MIME types are considered candidates for part deletion:
Anything with Content-Disposition "attachment"
Content-Type image/*
Content-Type audio/*
Content-Type video/*
Content-Type music/*
Content-Type x-music/*
Content-Type application/*
It has not been rigorously tested on various email providers, but it worked well for me. See the web page for usage details.