Maybe they have an exploration treaty with someone that already knows you.
Also I guess the warmongers among the races are supposed to be giant dicks who declare war on everything that is weaker. It doesn't matter how far away they are. You could argue it doesn't make sense, but you could also argue it keeps you on the watch because now you have to watch out not to go unguared near them with your scouts and stuff.
Personally I don't mind the behaviour.
