The unknown worst enemy thing doesn't require sophisticated justification, it's perfectly reasonable. I mean any human can figure out with easy logic who it was who gave our enemy techs before we met everybody, no espionage or alien intervention required.
If unsarcastic, This implies that the human player has some foreknowledge of the game already and the programmed personalities of the AIs. Even though I don't see how if I have a map and random opponents, how I could deduce who is trading with a civ I have met, when I have no knowledge who the other civs or leaders are in the game.
If, say, "random personalities" were checked on, then those who have only played Civ IV and spent some time knowing how the AIs settle, tech, communicate and war with each other would be able to eventually deduce who is who, after a time.
Regardless, then I see the argument as to this diplo hit being justifyable is that it's a balancer for the experienced human's ability to fairly quickly deduce once they have even the knowledge of who their opponents are the most probable outcomes as to what their long term strategies and agendas might be towards diplomacy.
Fair enough, I have no problem with that. But I would argue then that if it is a balancer, it wouldn't be justifiable as something that is being modeled by the game as realistic. In order for the opponent AI to be "clever" like the human and deduce from ....many times playing the game, that the human is up to no good...well, that would imply that ...how to put it...for the AI, "civilization" has happened multiple times, that the AI has 'squared off' with the human in multiple permutations of the multiverse, and that isn't the case.
Even so, one thing I can say about any rule, 'broken' or not, justifiable or not, is that diplo CAN be 'gamed'. Some diplo policies have to be adjusted. As a poster mentioned above, in a war, the human will be approached by both sides, and if the human doesn't want to get involved, will take -1 diplo hits across the board unless you mod the game. So, knowing that, you have game the system to survive by trying to figure out IF one should say 'no' or just declare a fake war against the AI most likely to lose and do the least damage long-term to your civ.
Likewise, the -4 "we haven't met you but we KNOW yer up to no good" hit can likewise be gamed.
If, for example, you are in 1000AD and not Saladin, say you are playing...Japan.....or Monty....thanks to foreknowledge, it's wise not to TRADE with saladin at all (unless you are mansa musa), and declare on him as soon as possible to become close buddies with the european union. (still, you'd want to get Christian ASAP, because the AP will still most likely cheese you on that scenario)....
you know...after saying all that, maybe if they just changed the text to "heyy...we eventually FIGURED OUT you traded with our worst enemy....-4" there....that's the fix