Reusing a USB Boot Drive - Format back to factory state?

You did not provide any information about which version of Windows you are using or about what sort of partitioning this USB drive is using.

If you are using Windows 7 then perhaps it cannot delete the partitions because your USB drive was GPT formatted by your Mac? If that is the case, then run DISKPART from an (elevated) command prompt. If a partition is READ ONLY or HIDDEN I don't think it can be deleted unless you force it. For example, use DELETE PARTITION OVERRIDE.

See the HELP for DISKPART for more info if you need it.

Of course, using dd from a Linux Live CD boot is also a way to clear the drive. FWIW, you don't have to write zeros to the entire USB drive. Just clearing the first MiB or so would do it. Adding count=2 to the example in hotei's answer should accomplish this.
dd if=/dev/zero of=/dev/usb_device_name_goes_here bs=1024k count=2

Unless I've screwed it up the above should write 2 blocks of 1024k (1MiB) zero bytes to the device you specify as the outfile (of=). This will wipe out the partition table whether it is GPT or MBR and then Windows can partition it as you wish.

Easiest way is to boot up a Unix/Linux live CD and then use dd to write zeroes to drive:

Insert drive into the USB port but do NOT mount it.

dd if=/dev/zero of=/dev/usb_device_name_goes_here bs=1024k

This will zap it back to it's original state. When Windows or Unix tries to use it later it will recognise that it needs to be "partitioned" and "formatted" and you can go from there.

Edited: If you're not familiar with Unix/Linux you should probably disconnect your hard drives before doing this just to be safe. Just connect the CD and the USB drive you want to format.