Gmail – Buying extra storage from Google for more than one year

No, there is no way to do this.

But, you can use filter import/export feature in Gmail to clone a rule then change the applied label.

1. Create your filter
2. Go to Settings > Filters
3. Check the checkbox next to your new filter
4. Click Export at the bottom, this will create an xml file called mailFilters.xml
5. You should have a file that looks like this:

<?xml version='1.0' encoding='UTF-8'?>`
<feed xmlns='http://www.w3.org/2005/Atom' xmlns:apps='http://schemas.google.com/apps/2006'>
    <title>Mail Filters</title>
    <id>tag:mail.google.com,2008:filters:11344473557977</id>
    <updated>2010-07-14T20:24:10Z</updated>
    <author>
        <name>John Smith</name>
        <email>test@gmail.com</email>
    </author>
    <entry>
        <category term='filter'></category>
        <title>Mail Filter</title>
        <id>tag:mail.google.com,2008:filter:1131773557977</id>
        <updated>2010-07-14T20:24:10Z</updated>
        <content></content>
        <apps:property name='from' value='foo@example.com'/>
        <apps:property name='label' value='the_label'/>
    </entry>
</feed>

All you need to do is to carefully edit this XML file in an editor which can intelligently handle plaintext.

Copy the code from <entry> and paste it in immediately after the first one. I removed the <id> and <updated> sections and they still worked, so much of the stuff in there is optional. Copy and paste a few more times, and you've got the result you want.

This worked for me:

<?xml version='1.0' encoding='UTF-8'?><feed xmlns='http://www.w3.org/2005/Atom' xmlns:apps='http://schemas.google.com/apps/2006'>
    <title>Mail Filters</title>
    <id>tag:mail.google.com,2008:filters:11344473557977</id>
    <updated>2010-07-14T20:24:10Z</updated>
    <author>
        <name>John Smith</name>
        <email>test@gmail.com</email>
    </author>
    <entry>
        <category term='filter'></category>
        <title>Mail Filter</title>
        <id>tag:mail.google.com,2008:filter:1131773557977</id>
        <updated>2010-07-14T20:24:10Z</updated>
        <content></content>
        <apps:property name='from' value='foo@example.com'/>
        <apps:property name='label' value='the_label'/>
    </entry>
    <entry>
        <category term='filter'></category>
        <title>Mail Filter</title>
        <content></content>
        <apps:property name='from' value='bar@example.com'/>
        <apps:property name='label' value='another_label'/>
    </entry>
</feed>

Save your file then click Import filters on the same Settings > Filters page and you will have the option of which of the contained filters you want to add.

Update: I don't have a query to find all messages with 2 or more labels. However, it sounds like you're trying to make Gmail behave more like IMAP (e.g. folders instead of labels). Instead of using "folders" in Gmail, I think you can continue using them as labels and your IMAP client will just adapt correctly, here's why...

Even though your mail client doesn't support labels, Gmail's IMAP feature compensates for this and allows the folders in your mail client to act as labels.

This means that some messages will appear in both folders, but will still be the same message (e.g. if you delete one, the other one will be deleted as well).

what [...] if I move a message from one folder (in the IMAP client) to another already containing that message?

According to Google's article, How do actions sync in IMAP?, I would guess that it simply removes the original label from the message and leaves the new one on there. Rather than having two messages in the same folder, you should only see one.

Or if I want to delete a message, not just remove a particular label?

According to Google's article, you move it to the trash to delete the message.