Self-answering the question. After years, I think I formulated a nice answer. The unicorn situation is not really symmetrical. I think this is an intuitive interpretation of Bayesian Inference.
Let's think of the world as an infinite series of rooms. The real world is not like that, but this approximation is sufficient.
In order to prove unicorns exist, we only need to find one room which has a unicorn in it.
In order to prove unicorns do not exist, we need to scan an infinite number of rooms. This is infeasible. The best we can do is scan some of the rooms. The more rooms we scan and discover to be unicorn-free, our confidence in "unicorns do not exist" increases. If we scan a huge amount of rooms, the confidence is extremely high, but we're never 100% sure. This is why scientists say "you cannot prove a theory". A theory is typically a claim that something is true in every "room". When the confidence is sufficiently high, some theories can be regarded as facts for all practical uses.
As a human, you've been here on Earth for quite some time, and you've scanned many rooms. You probably didn't find a unicorn yet. This is why "unicorns do not exist" can be regarded as fact. (This is also combined with other pieces of knowledge about mammals and how the world works, as other answers have explained).
If a 1-second old baby is fully rational, and that baby has not scanned any rooms yet, then its most rational bet is: There is a 50% unicorns exist, and a 50% they do not. This is why formally, given no further info, both arguments are equal.
So why is the method proving a claim so different from proving its negation? That's because "unicorns exist" in fact means "there is at least one room with a unicorn", whilst "unicorns do not exist" means "all rooms have no unicorns". Are these negations? Logically, yes. But to fully de-mystify symantics and language, note there are actually 4 possible claims here:
- Unicorns exist in at least 1 room. Easy to prove. Impossible to disprove.
- Unicorns do not exist in any room. Easy to disprove. Impossible to prove.
- Unicorns do not exist in at least 1 room. Easy to prove. Impossible to disprove. Already proven.
- Unicorns exist in every room. Easy to disprove. Impossible to prove. Already disproven.
1 and 2 are logical negations. 3 and 4 are also logical negations.