How to successfully store games on edge?
I've also been trying to fit more board games in less space recently.  Some notes so far:


The modern medium-square-box style of game works fine on the side in a bookcase; e.g. pretty much anything by Fantasy Flight or Days of Wonder.  Catan and similar smaller boxes will work OK even on their end.
Old-style flat/thin boxes (Monopoly etc.) really don't side-stack well.  (But frankly, they're also often inferior to modern game designs, so I don't mind leaving them at the bottom of a pile.)   Other games pile really well sideways on top of a Monopoly box.  If you're strong: Monopoly and Clue can go at the bottom, be pulled out sideways, and then the one you didn't play be lifted up along with all games on top of it to slide your chosen game back in underneath.
A lot of older games have bigger boxes than they need.  If you don't care about resale value, your Monopoly and Clue sets will fit just fine in the Monopoly box.  (If you're not bothered at all by losing the boxes, consider just getting a bunch of clear plastic boxes which do stack and repacking all your games in them.  Add some sticky labels on the sides and you're done.)
In limited space, start by packing the biggest games in a corner first, then work outward.  This makes the larger games less accessible - but they're often also the longest, least-often-played.
If rubber bands aren't working for you, try a long strip of velcro fastener... usually comes in the form of a long fuzzy strip with velcro on the end.  It'll wrap around the box and seal to itself.
If you play any small pub card games (e.g. anything by Cheapass or Looney Labs), get a single case you can carry easily to fit them all in.


(I've got all my small card games and Icehouse pieces packed in a single old vanity case.  Not only compact, but easy to take to the pub.)



My hints on internal organisation of the games:


Plastic baggies are OK for games with few counters, but clumsy for many.  Any craft shop will carry subdivided plastic trays in various sizes, intended for storing beads and the like.  They work very well for storing counters.


(For example, my Galactica set has the boards underneath with a plastic box on top with all counters and pieces divided by type, and the decks of cards lying rubber-banded alongside.  All expansions fit neatly in the original box and we don't have to sort out the pieces before play, just take out the storage box and leave it by the board.)


Card decks rubber-band just fine.  (Leave a couple of spare rubber bands in the game box for those moments when they snap.)
Consider preferring games with good storage trays built in!  (Small World and Dominion spring to mind.)