Hum..
Is this a new memory stick? I'm just curious because there have been very similar situations due to just manufactured faulted sticks distributed. If a quick format and a normal format doesn't help it whatsoever, it's probably faulty or has caused itself (no fault of your own) to become faulty. If it were a hard drive (which it isn't), I'd say to try to rebuild the master boot record; but, that's not the case - so you're kind of limited as to what interaction you have with the memory stick...
May I ask what brand/model it is?