What does an FFT artifact sound like exactly? I'm familiar with the notch, it's like your brain trying to fill in an empty space when nothing is there aurally. Or like when you're sitting in a very very quiet room and your ear scans for something to latch on to, but all you get is the noise floor.

No, brain does not use FFT, as it even has higher time/frequency precision that the transform allows for.
What you're descibing is not an "FFT artifact", just something known as temporal masking.
Have a read: https://en.wikipedia.org/wiki/Auditory_masking

FFT does not exhibit such issues, it's provably lossless on its own. You can apply inverse FFT with high enough precision math and you'll get the input signal, bit perfect.

Neurons are a nonlinear filtering system on top of already highly nonlinear cochlea and hair cells with uneven overlapping mapping between "ranges".
Have another, much more technical read on some facts of neural decoding/hearing:
http://www.jhu.edu/strucfunc/strucfunc/2011_files/2011_10_25%20%28handout%29.pdf
http://www.rle.mit.edu/media/pr152/31_PR152.pdf

Yes, human hearing is similar in this regard to cat's.

See Gabor limit, the variant of uncertainty that limits Fourier transform and any non-interference system. Our hearing bypasses this likely by resolving inter-band interference dynamically and having large amounts of band overlap, often more than one. Human hearing system also trades high short term dynamic range and sensitivity for many dynamic temporal artifacts. We have a kind of overlapping multiband dynamic range compressor built-in.

Likely the one who heard the first danger sounds lived more often, not the one who heard the second or third one... Similarly, positioning and distance cues have been vital and those use interference patterns a lot.
(Also a byproduct is we're very sensitive to signal harmonics, waveform shape and pitch, way more than most algorithms or measures commonly used. I'm actually battling this lousy guesswork/heuristic math at work, currently writing pitch shifters and pitch detectors. FFT is but a tiny building block and has many drawbacks - the logic itself is way more complex than just the analytic transform and FFT actually has major resolution issues in this use case, those have to be worked around.)

For such low latencies our hearing system has, microsecond even, people definitely have something way different, likely a system of nonlinear neural predictors, which is way too complex for even modern hardware to handle, not to mention we don't understand even a quarter of it well.

Not even just a single frequency, more like a relatively wide range of frequencies for each of them. It's quite amazing.
It is of course processed, but in a very different way.

I've explained it already. Temporal masking, nothing to do with FFTs.
In addition to the neural mechanism, the cillia themselves tune their sensitivity. (see those two more technical papers)

The mechanism is the same as if you've looked at the image on this page for minutes, then switched to a white page:
https://en.wikipedia.org/wiki/Afterimage