Any memory stick pro duo card 4GB or less should work with any PSP. Think it was somewhere in the 3.x firmware line that the limit was increased to around 8GB.

And there are two primary reasons why the size differences. One, the memory card maker is using a base 10 system to calculate size, while computers use base 2. So 4GB using base 10 math is 4000MB, but using base 2 math it's more like 4096MB. I might be a little off on my numbers, but you get the idea. Then above and beyond that, creating the filesystem so you can store files on the card takes some space.