Right, hopefully when JMAP arrives (soon!) you'll be able to use that nicely. It will give label-style handling by allowing the same message to exist in multiple folders.
Kinda hijacking this. When using FastMail with a custom domain can I setup a catch all address and then have each different address somehow tagged? It would be nice to be able to have proper unique email addresses for each service so I know where spam ends up coming from.
You can create an * alias in FastMail which will act as catch-all address. The received email will retain the original To: field so you can use rules to match them.