There's a few factors at play here:
Let's assume that we have a magical piece of software, which can listen to audio and tell us exactly what notes are being played. Even given this software, determining key is not a trivial problem. Sure, there are simple cases, but even humans disagree over many songs. A computer has no chance.
Take Sweet Home Alabama. The chords are D
C
G
. Many electrons have been wasted arguing over whether this is a V
IV
I
in G Major or a I
bVII
IV
in D Major. I personally think it's in the key of "please never play that again", so I avoid analysing the infernal thing too closely.
Or take Hey Jude. The na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na na bit. If we transpose a bit, the chords are also D
C
G
. But that's pretty clearly a I
bVII
IV
in D major. Context is important, and building an algorithm to automatically determine that context is a complex problem.
So, we've established that 100% of the surveyed songs with a D
C
G
progression are annoying. The next part of the problem is actually getting a list of pitches to do this key recognition.
You'll notice that I used the word "magical" in the previous section. Most pitch recognition software will do some sort of frequency analysis. Basically, they grab a section of audio, and determine what frequencies are present. We know the frequency of every note, so we can map that list of frequencies to a list of pitches.
Not so fast. Unfortunately, when an instrument plays a note, it produces more than one frequency. That's why a piano doesn't sound like a guitar. Some of those frequencies will be harmonic; that is, multiples of the root frequency. Others will not. If the instrument is not pitched (like untuned percussion, or a noise sweep), there will be lots of these inharmonic frequencies.
If you have a complete track, separating all these frequencies, determining which are pitches, and which are harmonics, is non-trivial. It's kind of like trying to separate the ingredients of a milkshake once they are mixed. It's certainly possible to get a good approximation, but hard to actually tell exactly what was being played. The (trained) human ear is much better at this task than computers.
Now, to be fair, if you're just trying to determine the key (rather than transcribe every note), this problem is easier to solve. I don't care who is playing what note; just the overall harmonic structure. But there's still plenty of room for your computer to make mistakes here.
A couple of comments have observed that even if you have a list of pitches, converting them to note names requires some idea of the key. This is because, in the vast majority of Western music, we have the concept of enharmonics. Basically, A# and Bb are the same frequency, and we choose the name based on the key.
For a lot of music, this isn't really a big problem. For example, here's a set of pitches:
A#/B♭/C♭♭
B#/C/D♭♭
C##/D/E♭♭
D#/E♭/F♭♭
E#/F/G♭♭
F##/G/A♭♭
G##/A/B♭♭
It's pretty obvious that this is B♭ Major. You could call it A# Major, but that's a much more complicated way to spell the scale, so we don't. Equally, C♭♭ Major is not a good name. That sort of heuristic is quite easy to add to software, so in this simple case, it's not really a problem.
It could be more problematic when there are two equally right options, like F# Major vs G♭ major. Again, either is correct, so you just pick one.
If the key is more ambiguous, then this could be more of an issue. But I think the other problems are much more significant.
Finally, on Auto-Tune. Auto-Tune's job is easier for a couple of reasons. Firstly, it's going in the other direction. It has a set of "good" notes (semitones, or a user-specified key), and moves any "bad" notes accordingly. It doesn't have to assign a key. Secondly, you generally autotune a single isolated instrument. That's much easier to handle than a complete mix. I don't know what Auto-Tune will do if you run it over the whole mix at once, but I don't think it will be pretty.
In short:
- Even given a list of all the notes/chords, key detection is non-trivial
- Getting that list of notes and chords automatically is not a reliable process
As a result, computers can certainly attempt automatic key recognition, and get close in a lot of cases, but it's unlikely that they will ever be 100% accurate. If someone would like to prove me wrong, I'd love a free copy of your software to verify your claims. For scientific purposes, of course.