Assuming this is a desktop computer, I have only seen an issue like this once in the 30 years working on computers, but it wasnt just a shift key. In the system I observed which was a 486SX 25Mhz back in 1996, you could start Windows 3.11 and open up word document and then random ascii would show up keyed. Swapping out keyboard didnt fix this, and clean installation of Windows 3.11 didnt fix this. In the end it was a bad keyboard controller chip which meant having to replace the motherboard.
But in your case you have only the shift key, and its doing this from both USB and PS2 and different keyboards, and you too have performed clean installation.
Thinking you too might have a motherboard that is having issues, just odd that its only the shift key, and is happening both with PS2 as well as USB, and that you are not getting a keyboard error at post diagnostics which the 486SX 25Mhz sometimes would display.
What is the specs of this computer, make/model? Some computers were built with faulty capacitors that can cause systems to act strange, and some models are very common to open and find swollen and leaking capacitors.