I've seen your problem with a Lexar 256mb Memory Stick Select (128mb x 2) reported three times before with this series of cameras -twice with a G500, and once with a KD-410z. I'm assuming you mean the Memory Stick Select, versus Memory Stick Pro. The factory firmware did not support Memory Stick Pro (but the new firmware does).
Anyway, if your card is the 256mb Memory Stick Select, your report makes 4 times I've seen users getbad ones. Call Lexar and they should replace it.
I'm using one of these cards with no additional startup delay (old firmware or new firmware). Some of the symptoms reported by others included the long (~10 seconds) startup delays, sometimes switching to the Secure Digital card.
Replacement cards of the same type worked fine for the other users.
One user did report that the new v3.38 firmware allowedone to work without slow startup or memory errors before he swapped his out, but I would still not trust it, even if the new firmware allows it to be used. Here is Lexar's support. I would suggest having them replace it:
See the 08-Dec-2003 14:36 entry in my pbase.com guestbook forsome differences in the codes on the cards, etc. (this entry is abouta user with the same symptoms as youare having):
BTW, if you have not upgraded your firmware yet, the new firmware allows the G500 to support the Memory Stick Pro cards, too.
P.S. -- If you decide to buy a larger Secure Digital Card for your G500, you will want to avoid most brands. I would go with a Panasonic or Simpletech card in 256mb or 512mb size (Simpletech SD cards use the same components as the Pansonic Cards in larger sizes).
Sandisk Standard SD Cards are not considered to be reliable in your camera (and many other manufacturers are using the same components as the Sandisk Standard SD Cards). Konica-Minolta used to approve them for use in sizes through 128mb, with specific warnings that the Sandisk 256mb SD may cause the camera to malfunction with errors. However, they have recently removed all Sandisk SD cards, in all sizes, from their list of tested cards for the G500.