Uhm... Which Memory Cards are you using? 8Mb SONY originals? Any of them is a cheap 64/128 Mb chinese one?
And which app have you used to format them? ffgriever's Memory Card Annihilator v2.0 is a very good one.
... and I suppose you have backed up your saves right?
PlayStation 2 [SCPH-30004 R, v5] + Network Adaptor (80GB HDD)
PlayStation 2 [SCPH-70004, probably v13] + modchip (probably MatrixInfinity 1.4 clone)
-- FreeMcBoot 1.8b, uLE 4.42d, OPL 0.9.1, SMS 2.9r4 --
PSP 2004: TA-085v2 (semi-bricked)