So it seems that our brains don't exactly "trust" deductive reasoning. Maybe because problems in the ancestral environment didn't have clean, logical solutions?

Arguably, problems in the modern environment don't have clean, logical solutions either! Note also that people get good at games like minesweeper and chess through learning. If the brain was primarily a big deductive logic machine, it would become good at these games immediately upon understanding the rules; no learning would be necessary.