IMHO:
Int vs. Wis
Reason vs. Common Sense
Knowledge vs. Perception
Logic vs. Will
As per the PHB (3.5), Int "determines how well your character learns and reasons."; Wis "describes a character's willpower, common sense, perception, and intuition."
The very high Int PC would be a well-educated problem solver, following rational, logical means to provide solutions.
The very high Wis PC would be an intuitive, perceptive person with a strong force of will (perhaps through stubbornness, perhaps through discipline, or perhaps through belief/faith) who provides a direct, simple solution that's based off of practicality or observations of the situation at hand.
It's feasible that both would provide the same answer to a problem, but they would have come to that conclusion through entirely different methods/processes. The high Int character would apply knowledge gained to the matter & provide the answer based on the variables presented in that particular cicrcumstance. The high Wis character, OTOH, would apply experience and personal observations of the matter at hand and, through common sense, deduce an answer from the clues presented.
Now, within certain areas/realms of knowledge or issues, one would be better suited to provide an answer than another.
Let's look at this another way: Spot & Listen are Wis-based; they use the perceptive/intuitive aspects of Wis to succeed. Search is Int-based; it is based off of knowledge of what certain things look like, what could be placed/hidden where, etc. (essentially, knowing how to look for certain things, and knowing what to look for).
So, the high Int character could use applied knowledge and research to find/determine possible events/outcomes/theories/information to a question/problem. The high Wis character, like a good detective, would use experiences, observations made now and in the past, and certain clues gained over time to determine an answer/solution to a question/problem.
Now, a character that had both a high Int & Wis would use both of these abilities together to solve problems/deduce answers. This, IMHO, is a hallmark of the "great detective" characters (Sherlock Holmes, Batman, etc.); someone who uses their reason/education and detection/perceptive abilities to solve mysteries or find solutions out of very tough problems (like determining a motive for a crime or escaping a massive death-trap).