Of course, you can purchase more space at a reasonable price. Also, I've found backupify and findbigmail, and there's the download via imap and delete option outlined, for example here.
What I really want is to download any large attachments to a back-up, and strip them from the emails, but leave the text of the message in place for searching. Any services that do that? Or any other ideas?
You have two options:
There is a thread on Gmail help dealing with this exact issue: http://www.google.com/support/forum/p/gmail/thread?tid=2d69c50302cf0e14&hl=en
Google has an engineering team known as the Data Liberation Front.
The Data Liberation Front
The Data Liberation Front is an engineering team at Google whose singular goal is to make it easier for users to move their data in and out of Google products. We do this because we believe that you should be able to export any data that you create in (or import into) a product. We help and consult other engineering teams within Google on how to "liberate" their products. This is our mission statement:
Users should be able to control the data they store in any of Google's products. Our team's goal is to make it easier to move data in and out.
The specific information on Gmail says that IMAP is the preferred choice for liberation (or backup in your case). Almost all email clients will support IMAP (or POP if not).
Escaping from Gmail
IMAP, POP Access
It's easy to use a different email reading program with Gmail using either IMAP or POP, or to get all your mail out to take to a different provider. Go to the Settings page (link at top right of Gmail page), Forwarding and POP/IMAP tab.
This tab lets you set up POP and IMAP, with instructions for popular email reading programs. There is extensive online help available for both POP and IMAP.
