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.