The phones you are talking about are the older phones. No new Nokia phones chokes with a 4gb card. In fact you'll find a few people on this forum who are happily using 8gb cards in their Nokia phones.
The N96 I talked about may be upcoming, but by no means it is a concept or something. It is as real as it gets and is just a month away from its launch. You can find several videos of it on Youtube.
The 32 gb limit is not just for the N96. Any device which supports the HC (High Capacity) standards, like all new Nokia phones do, support upto 32gb. And that too without slowing down. If a company claims to support the HC standard, it has to make sure that it can support it without slowing down or anything, that is the hardware has to be capable enough. Otherwise it cannot support HC. As for thickness, the latest Nokia E71 is 10mm thick (thin?) but still accepts microSDHC cards. And there are other phones too which are just as thin as the iPhone or even thinner, yet support high capacity cards.
iPhone's storage space is not a negative. 8gb and 16gb are enough. But for some even that is insufficient. There is no such thing as sufficient storage space. It's always more the merrier. Ask yourself. You ordered your iMac with the optional 1 TB HDD, didn't you? Why? Because storage space always finds its uses and you soon run out of it, no matter how much it would be.