I'm pretty much in agreement with the other great ideas that have been put forward in this thread, although I have some tweaks for the implementations as they are proposed. In this light I thought I'd add my 2c.
Vanity gear sets
Although a variety of items drop, the amount of actual models that exist in the game is far less, the items that actually drop are mostly recolours and stat differences. The main reason to keep these sets around in your storage is pretty much exclusively for transmogrification or RP purposes, or sentimental value. Items that have sentimental value as a 'conventianal' item (meaning with its stats intact) can be put in the void storage so they are not the issue.
To solve this issue, I would suggest a system where you can have the transmogrification vendor 'learn' a certain item model and colour that you have obtained, for a small gold fee, which also removes the item itself. In exchange, you will be able to freely transmogrify any new items you bring to the transmogrification vendor, at the usual transmogrification cost. In this system the amount of data that is stored on the server is still increasing over the current situation, but I feel that this is unavoidable if the goal is to implement something that gives either equal or improved storing capacity compared to the current implementation. Major advantage is that the server only needs a bunch of 'checkboxes' that remember whether or not you taught the vendor a certain model and if yes which colourations you taught it. This same system could also be used for the 'vanity' tabards if coupled with a new 'blank tabard' item that you could buy from a tailor or vendor and then transmogrify into any of the tabards which you've 'taught' to the vendor. The few tabards that have an 'on use' effect or an active effect can then be excluded from this or perhaps even be allowed to be transmogrified to look like another tabard.
Effect: Removed space taken up by vanity gear, removed space taken by tabards, minimal impact to server side storage needed per character
As many people have made clear, with the new cooking materials from Mists of Pandaria we're quite simply running out of space to put all this stuff. In addition, it feels clunky that you have to take stuff out of your bank to craft with it and send it to another character to have that character use it.
In this respect I feel that the solution implemented in the recent update of Guild Wars 2 is the best, both from a usability point of view and from a technical point of view. To reiterate, in that game you get an account-wide storage for all of your crafting materials, one slot for every 'material' with substantial stack sizes (although the stack size in that game is currently still too low to truly eliminate the issue). When you start crafting, any materials that are in this storage are freely available for use in addition to any materials that may be in your bags. Ideally you would be able to send materials to this storage in the field at the click of a button, but even if you had to go to a bank to deposit the items it would be a huge improvement over the current system. On the technical side this allows a similar implementation to the previous: you simply keep a list of possible crafting materials along with the amount that the player has collected. Since it is central storage, players will not use up as much of their characters' storage real-estate meaning that overall less data will need to be stored.
Effect: Removed space taken up by crafting materials, higher quality of life for crafting by removing the need to mail stuff around, possible decrease in server side data storage needed per account.
Some tokens are still implemented as actual item drops where they could easily be made into currency.
Turn them into currency. Gear tokens would probably need to be excluded from this to avoid excessive UI complexity.
Perhaps the functionality of the auction house and trade window could be expanded to allow a select few currencies to be sold and/or traded. Either that or some sort of system could be implemented to allow a player to convert those currencies into items that can be sold/traded...although no items currently come to mind that have this functionality today and I'm not sure this would actually add much.
Effect:Unified experience, removed space taken up by tokens
The last culprit taking up lots of valuable storage real-estate are the numerous toys and 'fun' items. Although we can't do away with the various iterations of the 'fun rock' there is a lot to be gained.
As many before me have noted, in the current UI it would make sense to simply add another tab to the mounts and pets window where we can have a list of all those fun activation based things so that we can simply click on the fun item we want.
Effect: Removed space taken up by toys etc., scales wel into the future
Role specific items
For classes that have different talent specialisations or roles within those specialisations (looking at you, feral druids ^_^) bagspace can quickly become a problem. Imagine a raiding druid with a feral offtank/dps spec and either a restoration healing spec or a balance dps spec. This poor druid will potentially need to carry around 3 full sets of gear, 3 different kinds of buff food, at least 2 different kinds of flasks or elixirs and probably some extra trinkets since some are often situationally better than others. And we're not even taking into account the fact that this druid might also be carrying some spare enchants and gems so that when a new piece of gear drops for them they can immediately start using it.
My proposed solution here is twofold. Firstly, I would suggest allowing people to equip specific gearsets for each talent specialisation, with the option to have items shared between the two. This way our feral druid will only have to carry around one extra set instead of two and most people can make do with no extra sets at all. At the same time, those who pvp but don't have a full set of dedicated pvp gear can still have a normal spec and a pvp spec and share some of the items between the two without much hassle.
Secondly, I would suggest some extra space (perhaps extra slots on the character's gear screen) where the player can store consumables for that particular spec. A protection warrior for instance would have 5-6 slots that can hold tanking flasks/elixirs and food that gives buffs like stamina or parry, but not intellect food etc.
Effect: Removed space taken up by multiple gearsets, removed space taken up by spec-appropriate consumables, slight increase in server side data storage needed but scales well into the future
If all this is implemented, how will things be?
While questing we will still carry pretty much everything that we receive, except perhaps crafting materials if that change is implemented. Still, we'll have saved some space since toys don't take up space anymore. Since we can have multiple gearsets 'equipped' we can quickly hop into a LFD, a group quest, a battleground, or whatever we like to do most often. If we want to clear up some space, we need to go to a city and visit the appropriate NPC's, pretty much as it is today. If we want to craft, all we need is to make sure that any secondary crafting requirements are met like being near an anvil or forge or being in a certain location so there's not much of a change there, except we can now craft anything we have gathered materials for on our account.
If we don't have a lot of money and vanity stuff we can still choose to stockpile everything in our bags and bank, but in future expansions the amounts of fun stuff and cool gear can be increased without any impact to bagspace since we always have the option to have the appropriate vendor take care of our not-so-phat-anymore loots for us. If we're the kind of player that likes to collect all the steamy romance novels, or all plate armors with a name starting with an 'a', we can still satisfy our obsession but 'joe average' will never run into any storage space problems ever again.
overall, the amount of storage space each player's account takes up should be roughly the same as it is today. Since so many things are now turned into lists, it might even be possible to reduce the actual bag and/or bank space the player has so we can save some database real-estate there. The increase of database storage in the future will be minimised since most people will use our new features to store their old gearsets and those are simple 'checkbox lists' anyhow.
Apologies for the wall of text, I hope it helps someone ^_^