I was just wondering how much memory a NES game uses, since judging from ordinary .nes files the game rom is not larger than a few kB. Is lack of memory ever an issue if you just want to download the really old games? 

I dunno, but if you only buy NES games. You can probally have at least 10-15. Well I think, not really sure.

You would fill up all of the channels on the wii main menu before you would run out of space if you were downloading NES games only. They are VERY small. Very, very small. It's when you start getting into WiiWare, N64 and NeoGeo games that the 512 MB flash starts getting full.

You can fit way more than 10-15 NES games.  I have 16 total games (which has the memory pretty much filled), including 2 N64 titles (Sin & Punishment, Mario Kart), and one Wii Ware title:  Strong Bad.  Most of my games are TurboGrafx-16, Genesis, or SNES.

At any rate, the real answer is, "no matter what, you simply can't fit enough games onto the Wii."

Because there's isn't room for an impressive collection.

NES games I think you should be able to fit close to 100 in the memory.... but the number of channels is limited so your total will be 48 minus whatever main channels you have (Disc, Mii, photo, forcast, news and shop are obligatory) so 42 maximum.

SNES games are on average double the size (in blocks) so you should still be able to fill all 42 channels with SNES games.

I have 63 blocks left and I have 10 VC games, all channels, a bunch of games and 2 WiiWare games. You should be ok for now.

My VC games are

1 - NES
1 - N64
1 - SMS
3 - SG
4 - TBGFX16

Super Mario Bros. 3 takes 27 blocks, and is probably among the largest of NES titles. Most will take less than that. The largest games I have downloaded are Sin & Punishment (287 blocks, I think) and Ys Book I & II (273 blocks?).

I have 17 games total: 5 N64, 5 SNES, 4 NES, 1 NEO-GEO, 1 Turbografx, 1 Turbografx CD; these, along with some of the downloadable channels (internet, etc.) and Brawl's giant save file take up almost all of the available memory.

I deleted games for the first time today to make room for "My Aquarium". I feel dirty inside. Yoshi's Story and Mario Kart 64 (and the Check Mii Out Channel)......gone. I deleted Paper Mario for the Nintendo Channel.

I wish I could fill up the empty channels, but Nintendo won't let me. It sucks.

I'm a Virtual Console addict and now everytime I want something new... I've got to delete one or more games. Fortunately, if I want those games again, they'll be free but it's such a pain having so little space.

Also I'm scared of deleting games with save files because I'm not sure if they'll still be there when I download them again.

The save files are seperate. Look at your Wii memory.  the Channels are under the "Channels" section (obviously), but the save files for downloaded software appear under the regulare memory.  Most save files for VC games are only 1 or 2 blocks since most are just based on the emulations.  You retain those when you delete a VC game.

But it's asinine that we should even have to delete a game just to buy another one.  Nintendo's initial (and so far, current) storage decision for the Wii is really counter-intuitive.  I can't believe they were smart enough to have Wi-Fi out of the box, but so stupid to limit the storage space.  I'm sure the computers they used to develop Mario Galaxy had more than 512 megs of space...