What happens exactly to a USB stick when it's formatted?

When I format a USB stick then I wonder what has happened.

I know that the stick is divided in blocks of a certain length, but I don't know whether something is written to all these blocks, that makes the data unrecoverable.

There are programs of which the writers claim that they can recover what has been erased from a USB stick, but I never saw it work.

So my questions are:

1. Is it possible to recover data from a USB stick after deletion?
2. Is it possible to recover data from a USB stick after formatting?
3. Is the data (partly) shredded after formatting?
4. Is there in this case a difference between FAT16 and FAT32?

 

Yes
Yes
Yes
No

 

With HDDs there was/is that debate whether once overwritten data can be restored. Not so on flash storage, overwriting data means it's definitely gone.
AFAIK when selecting full format in Vista/7 the partition is zeroed out.
Therefore:

yes
depends
depends
no

Another thing to keep in mind is wear leveling, I don't know how to mitigate this risk short of physically destroying the media.