I did not have luck with the other methods (diskpart
got stuck in the "On computer" part for some reason) mentioned here, but this program worked perfectly and fast:
SD Card Formatter (which, despite the name, works for USB sticks too):
https://www.sdcard.org/downloads/formatter_4/
It took all of 5 seconds to format it back to normal state after having a bootable Linux on it, which I created in Linux Mint.
The steps:
- Install the program
- Select the drive of the USB stick
- Keep the default "Quick Format" option selected
- Click "Format" in the program
- Done!

I found the program in the same guide mentioned in TechLife's answer:
https://www.pendrivelinux.com/restoring-your-usb-key-partition/
