we used python to generate a Bitcoin private key
Python is a programming language. You should be more specific in what you did.
then imported the key into the electrum Android app, sent btc there and forgot about it.
I take it you don't have the same Android app anymore?
I have been trying to recover that address but the private key doesn’t generate the same address anymore.
This is exactly why I like to verify my backups
with different software to make sure I can restore my backup before funding it. I know it doesn't help you now, but you should use it next time.
I have to ask: why didn't you let Electrum create it's own wallet with private keys, instead of using a non-standard setup?
I have used python to generate 5 different legacy addresses but all are different from the very first one.
Again: be more specific. Did you create 5 different legacy addresses from the same private key? That's not possible. Or did you create 5 new random private keys? In that case it's no surprise they're different.
I am very sure it’s the right key because there are multiple backups. Is it possible that the address format is no longer supported and hence difficult to recreate with modern tools? Does anyone have any insight into this and what may be the possible problem???
Chances are you created the wrong address. From the information you gave, I can't tell you what went wrong. Bitcoin legacy addresses didn't change.
Is it possible that electrum android app uses a different architecture to generate a public address now or it had a bug that generated a wrong address for then?
It's possible you downloaded a compromised version of Electrum. If you check your address on a block explorer, is the balance still there?