I also asked this question over on SuperUser (partly to kick start my account over there) and got the answer. This is the relevant part of the answer:

That support page is misleading. When it says if the tool returns the message:

"This operation may find that this database is corrupt"

It means does the output contains that text somewhere? Not is that the only output. The output will still look mostly like the second sample, but with the line above somewhere in the output. Even if the tool finds possible corruption, it will still end the output saying "Integrity Check Successful".

So all sorted now. I should have tried that straight away, but the support page appeared to be clear cut about which solution would work.

For Git Bash

If you are running msysgit (I am assuming you are) and are looking to run Git Bash (I recommend it over TortoiseGit, but I lean to the CLI more than GUI now), you need to figure out what your home directory is for Git Bash by starting it then type pwd (On Windows 7, it will be something like C:\Users\phsr I think). While you're in Git Bash, you should mkdir .ssh.

After you have the home directory, and a .ssh folder under that, you want to open PuTTYgen and open the key (.ppk file) you have previously created. Once your key is open, you want to select Conversions -> Export OpenSSH key and save it to HOME\.ssh\id_rsa. After you have the key at that location, Git Bash will recognize the key and use it.

Note: Comments indicate that this doesn't work in all cases. You may need to copy the OpenSSH key to Program Files\Git\.ssh\id_rsa (or Program Files (x86)\Git\.ssh\id_rsa).

For TortoiseGit

When using TortoiseGit, you need to set the SSH key via pacey's directions. You need to do that for every repository you are using TortoiseGit with.