We can do the same thing for a parking lot problem as we do for Fermat's Last Theorem.
Suppose we want to determine whether one of the cars is both orange and not orange (see note). I don't think anyone would need to go through the parking lot or even give so much as a cursory look to any of the cars.
We can do the same thing for a mathematical problem as we do for your parking lot problem. Suppose we want to know how many even integers there are. Well, we could just go through the set of integers. We wouldn't finish the job but we wouldn't finish a parking lot problem either if the parking lot had an infinite number of cars in it.
And, for maths problems, it is simpler for some of them to just count on our fingers than to try and solve the thing logically. For example, how many 1's in the first one hundred digits of the decimal part of π?
It is a mathematical problem since there is likely a logical solution to it, but, like your parking lot problem, it is also one you can solve using an algorithm because it is a finite problem.
However, it is precisely the method you use to solve a problem which is either mathematical or not mathematical.
Mathematics is both logical and formal. It is also fundamentally an abstraction and therefore a generalisation. The same theorem applies to an infinity of possible concrete situations. Logic isn't specific to mathematics. Any problem we solve requires some logic. Formalisation isn't specific to mathematics either. But mathematics involves these three aspects.
It is also an extreme form of generalisation. Science also relies on abstraction: a necessarily small set of observations and experiments make the basis for generalising to a particular type of phenomena. Mathematics goes well beyond that. The same mathematical theorem or theory will potentially apply to very different species of phenomena. You can count cows just as much as atoms, and the whole of arithmetic applies just as well to cows as to atoms.
This in turns requires that mathematics, unlike science, completely ignores empirical evidence (except of course, if it is applied mathematics).
So, mathematics is a discipline where people assume abstract premises, often called axioms, expressed in as rigorous a way as possible using an often specially made-up formalism and go on logically inferring from that perfectly abstract and formal conclusions, i.e. theorems, that potentially apply to many completely different types of real-world phenomena. Something only mathematics and Aristotelian logic can do.
There is also a number of mathematical problems that still don't have any known mathematical solution. One of the most well-known and perplexing example, given its apparent simplicity, is that of the prime numbers.
A prime number n is a natural number, i.e. a positive integer, which is not equal to the product of any two natural numbers other than 1 and n itself. For example, 2, 5, 17, 53 are prime numbers. 12 is not a prime since it is the product of 2 by 6, or 4 by 3, or indeed 2 by 2 by 3.
So, we can give a proper definition to the notion of prime number and assert confidently that if n is a prime number, there are no two natural numbers p and q, other than 1 and n itself, such that n = pq. However, there is as yet no known formula to identify all prime numbers. We don't know of any algorithm listing all prime numbers.
Of course, mathematicians are perfectly capable of deciding whether one particular number is or not a prime. However, what they seem interested in is a formula for listing all primes. They already have discovered various formulas to identify a number of subsets of all primes. But no general formula yet.
Existing formulas leave out an infinity of prime numbers. You have one parking lot with an infinity of cars and you also have several infinite lists of orange cars together with their location in parking lot. This is a lot of orange cars you know where they are. However, there is still an infinity of orange cars not on any of your lists, somewhere in the parking lot you don't know where.
Thus, for an infinity of cases, to know whether a number n is a prime or not, you have to use your parking lot procedure to try and see if it is or not divisible by any of the natural numbers between 1 and n.
This is a cumbersome procedure. A formula would be much more convenient, be less exhausting, give the result faster and with less risk of error. Discovering whether one number is a prime or not, however, is not the job of mathematicians. The job of mathematicians is to find the general formula once the premise of the definition of prime numbers is accepted (and given all other accepted premises relative to numbers).
Could "orange and not orange" fail to be a contradiction, voiding my point?
Cars could be painted not at all with orange paint but looking orange from a distance for example...
Yes, what colour things are is nothing like a black-and-white issue... However, I did say "orange and not orange", not something else.
So, let's assume cars may be painted with yellow and red dots all over and look orange from a distance. Even then cars will either be orange or not orange, and this whatever criterion you decide to use to assess whether a car is "orange".
The argument that red and yellow dots would make a car both orange and not orange, which would therefore make the predicate "orange and not orange" true is the fallacy of equivocation.
The equivocation is in having, if only implicitly, two different criteria to assess whether a car is orange. You can't do that. You have to use the same criterion not only for all cars but for "orange" and for "not orange". The criterion may be "looks orange to me", or "is painted with orange paint all over", or indeed anything at all, like, is painted black, or "smells good". This is how, and indeed why, logic works. But it will only work if you use it to begin with.