From the info you provided, GRUB may not be the issue. It might be a poor implementation of UEFI by the computer manufacturer. Attempting to manually reinstall or fix GRUB would not help if this is the case.
Try installing rEFInd onto a USB drive and booting it (assuming your computer can boot from USB). Follow the instructions and links at http://www.rodsbooks.com/refind/ to download and install. I recommend using the USB image file. There's a good chance rEFInd will find your Debian installation and kernel image and present an option to boot it.
Afterward, if you want rEFInd as a permanent solution:
- log into Debian and get sudo/root access
- mount the rEFInd USB drive, open it, and cd into EFI/
- copy the "refind" folder and paste it to your system's /boot/efi/EFI directory (make sure your ESP is mounted at /boot/efi). This will prepare us to "install" rEFInd using EFI shell.
- Reboot computer and boot the rEFInd USB drive again
- Choose the EFI shell option
- Follow the instructions to install via EFI shell here: http://www.rodsbooks.com/refind/installing.html#efishell
This will update the nvram/computer's boot options with an entry pointing at Debian.
You may run into root access issues that need fixing first before you can install rEFInd on the main system. In my own experience, Debian's install process didn't enable root access despite me confirming otherwise. I'll leave this for some other time. As to why Windows and Mint worked before, if they were both on the same ESP, I'm guessing the UEFI detected Windows's presence and so was able to see other systems. If Windows was not present, it wouldn't have seen Mint (and therein lies the problem).
I had to do a lot of research for this because I'm assuming few people own hardware with poor UEFI firmware, so this issue is rarely reported and asked about. This is my two cents in order for me to give it more exposure. I hope I was able to help. I'm definitely not a Linux expert so feel free to correct anything I may have wrong. Anyway, good luck!