The key whose key-id is in the signature did not s

I'm trying to sign my git commits, but when I push them to GitHub they have the Unverified badge and

The key whose key-id is in the signature did not sign this commit. Someone may be trying to trick you. GPG key ID: mykeyid

I find this quite cryptic, in my world the id with which a commit is signed will appear in the signature, as the key with that id signed the commit!

Question How is this possible, and how do I solve it?

I especially want to be able to sign commits automatically from within my IDE, without needing to enter my passphrase every time.

If interested, here is a summary of the relevant steps I did. The first few coincide with GitHub's guide for signing commits.

Generate key pair, add GPG key given by --armor --export to GitHub account
Update git config with user.signingkey.
Set commits to be signed by default with git config --global commit.gpgsign true.
The gpg version that comes with git is too old, I installed gpg 2, checked with gpg --version, I updated GNUPGHOME just in case.
Made a script C:\Users\username\gpg-no-tty.sh and put into it echo mypassphrase | gpg --passphrase-fd 0 --batch --no-tty --yes "$@". Couldn't find anything better than a plaintex password.
Point git to this script with git config --global gpg.program C:\\Users\\username\\gpg-no-tty.sh.

Verifications

Important: I verified that git verify-commit HEAD shows the same ID as the signingkey in my git config which is the same as my GitHub GPG key shows in settings. (It also outputs a warning gpg: WARNING: unsafe permissions on homedir)
Also important, as Ferrybig mentioned in a comment I checked that my email in my gitconfig is the same as used for my gpg key is the same as used as primary (verified) email in GitHub.
As Jens Erat mentioned in a comment, you can also use the fingerprint (40 character string) instead of the long id (16 characters) as outputted by gpg --list-secret-keys --keyid-format LONG, I tried this in my gitconfig but it didn't help.

gpg-agent

As Daniel H suggested in the comments there is something like gpg-agent which should remember your passphrase, and this is what I tried:

Add use-agent and no-tty (had something to do with my IDE not expecting a console interface asking for password) to C:\Users\username\.gnupg\gpg.conf, change gpg.program in my .gitconfig to gpg
Add to C:/Users/username/.gnupg/gpg-agent.conf the time to live: default-cache-ttl 34560000 and max-cache-ttl 34560000
I get gpg: gpg-agent is not available in this session, and didn't find yet how to solve it. Both gpg-agent and gpg are version 2.2.1 so that's not the problem.
According to some sources, for gpg version > 2.1 the environment variable GPG_AGENT_INFO needs to point to C:\Users\username\.gnupg\S.gpg-agent. I did this and rebooted. Now I get gpg: gpg-agent protocol version 0 is not supported.
I added :1 to that path and now I get gpg: can't connect to 'C': invalid value. This doesn't make any sense to me. What is C and where does it come from? Is the my drive letter, so gpg tries to execute the path as an object?

You can either just put no passphrase on your key when you create it, or you can try gpg-agent. For me it didn't work, I still had to provide a passphrase but it's worth a try:

Update git to at least 2.19.1 because it includes gpg2 now, make sure you use git's gpg and try to use gpg-agent again - it should work now. Only step 2 of your 'gpg-agent' steps should be enough.

You might need to remove your ~\.gnupg directory including keys if you run into migration problems (beware the error messages can be very misleading), so you can regenerate everything (including keys) using git's gpg.

I have written the complete instructions in this answer.