I'm using a 4Gb class 2 that came with another Nokia I recently bought. A bit slow with the pictures (I have a few hundred of them). But so far no other problems.

I heard Toshiba makes good memory devices. And class 4 (speed) should be sufficient for mobilephone use.
http://www.toshiba-memory.com/en/micro_sd_cards.html