Sometimes it is necessary to go to the command prompt (!) to accomplish things, even in Windows.
If there is any invisible junk, like old partitions, on the stick, the GUI utilities in windows will not be able to remove all that.
In this case go to the command prompt (as an admin user), and do the following:
diskpart list disk select disk # clean create partition primary select partition 1 active format quick fs=fat32 assign exit
make sure that you get the right drive with the select disk command, otherwise there might be a long night of re-installing windows.