ML Algorithms to discriminate "known" from "unknown" instances
I would use a two-step pipeline where the first step discriminates between known and unknown and the second step performs the actual classification. This approach has a number of benefits.


Separating the two problems allows you to judge the accuracy of each step. You can assess the quality of your known/unknown discrimination independently of your actual classifier and vice versa. This will tell you where you need to focus your efforts.
You don't need to worry about your classifier being over confident for examples you aren't actually interested in since presumably you're taking care of this beforehand.
The known/unknown discrimination is just the problem of outlier detection. There are lots of ways to approach this and you may be able to find methods designed to work within your specific problem domain. I frequently hear 1-class SVMs (support vector machines) come up in this context, but have never worked with them personally.


If you think about the way decision trees work it is pretty easy to see why a single tree is going to be overconfident. There are lots of different ways to learn decision trees, but in general you can think about them as trying to make the leaves as pure as possible, i.e., we want the leaves to contain instances that all have the same class. Since an unknown example is just going to follow some path down the decision tree, it will end up in a leaf, which by construction, contains little class variability. From this observation it is easy to see why combining many different trees (like in Random Forests) is going to help avoid this problem.

As for why Naive Bayes is being overconfident, I would guess this is due to some combination of one of the class priors $P(y)$ being larger than the others, and/or having most features be unknown for your unknown example (so $P(x_i|y)$ is approximately the same for all $y$ and most $i$ if you're smoothing the estimates) and a couple show up in one class causing the $\prod_i P(x_i|y)$ term to blow up for one $y$ relative to the others. This is just a guess without the data.