This is a classic ruba d'leisa kaman. In the overall population, a very, very small number of animals are prohibited. Knowing nothing else, presented with an animal before us, we assume it is permitted.
(This is known as "leisa kaman", "it does not appear before us", as the negative outcome is a theoretical. A weaker form of rov is "ruba d'isa kaman", "a majority appearing before us", e.g. we know that there is one non-kosher item mixed in with these ten kosher ones, but we don't know which is which.)
The Gemara in Chulin uses the concept of ruba d'leisa kaman with regards to checking for treifos. An animal with a brain aneurysm is going to die soon and is a treifa, therefore not fit as a sacrifice; however for a korban olah we burn the brain whole, rather than dissect it. Isn't there a small chance this animal is invalidated? We don't concern ourselves with that chance.
If we need not concern ourselves with the miniscule theoretical probability that this cow has a brain tumor, then we also wouldn't concern ourselves with the miniscule theoretical probability that it was used as a harlot's wage or as barter for a dog. (Unless you're living in a time or place where that's incredibly super-duper common.)
