Hi Difusal,
I am inclined to think - rightly or wrongly, I do not know :) - that your pendrive perhaps has some sticky first sector (MBR) and that could be the reason for the problem in formatting it.
Can you upload the screenshot of how it looks in the Windows Disk Management?
Disk Management - Post a Screen Capture Image
Though you have said that a lowlevel format was done
( curious to know which program you used for it) and also a regular format was tried with HP USB Disk Storage Format Tool
( Did you run it as administrator? ), try the same process, this time with Bootice
Download Bootice 2012.12.12 Free - Modify, backup, restore the MBR and PBR - Softpedia
It is a standalone Windows executable.
Plugin your pendrive. Just (double) click on the Bootice executable to run.
In the GUI, click on the Utilities tab and then Select and Fill.
In the Sector Filling dialog box, choose Physical disk, check and select the correct drive, select Fill with 00 and click on Start Filling.
If filling is successfully done, click on OK and OK in the subsequent dialog boxes. Close the Window to take you to the main GUI.
Open the Physical Disk tab, check the correct destination drive is selected and then on Parts Manage.
In the ensuing Partitions Mnagement Window, click on reformat USB disk.
In the Removable disk repartitioning window, select USB-HDD mode (Single Partition), select the File System, give a Label and then OK.
It should now complete the formatting.
Close Bootice.
I place immense faith on the HP USB Disk Storage Format Utility and if it is not able to format I would say the drive is beyond repair. But here I am not sure whether you ran it as an administrator.
Now the above procedure I had enumerated is purely experimental to check whether it helps.
Good luck.