hace un tiempo un conocido tuve ese problema con windows, y tuvo que utilizar una distribución linux ubuntu, y solo a travez de ubuntu pudo formatear el pendriver, quizás debas recurrir a la opción de bajar la versión live cd de ubuntu:
http://ubuntu.softonic.com/linux
porque normalmente el programa que te indique, debería poder darle formato, siempre y cuando windows lo reconozca bien, igual trata antes usando un antivirus para memorias usb, por si acaso queden rastro del virus que te afecto el pendriver:
http://usb-security-utilities.softonic.com/