What do "Batél Beshishim Lechatechila" and "Mevatél Issur Lechatechila" mean?
Batel BeShishim - this means means that something is nullified one part in 60. So one part of something forbidden to 60 parts of something permitted. This is derived from a verse, but the idea is that once something is one to sixty you can be assured that the taste is not there.
The classic case is if a drop of milk spills into a large pot of meat stew - if the drop of milk is less than 1 to 60 then the mixture did not become forbidden. There are limitations to this principle (like if the problem can be found and discreetly removed or if the item is a flavoring ingredient and thus has a stronger taste than typical for its volume), but that is the idea.
One important point of this is that it is only permitted if it was done by accident or without intention to remove the problem. So Batel BeShishim LeChatchila is the idea of doing this mix on purpose.
Mevatel Issur LeChatchila is the general idea of doing something to remove the prohibition of some mixture without actually removing the forbidden substance. So lets say, in the above example, a piece of butter fell into the meat stew (less than 1 to 60). You could remove it before it melts, but instead it is mixed on purpose into the stew and melted in. Well, if that happened by accident, it would be fine, but since this was intentionally done it creates another set of problems, with only specific circumstances permitting it.
Another example of the latter that doesn't involve the 1 to 60 ratio is an infested produce where the bugs are already less than 1 to 60. It is still forbidden to eat that as long as the bugs are whole, so in order to remove the problem, the produce could be pureed (or according to some, frozen) to break down the whole bug into parts, thus permitting the mixture. Again, this can only be done in a limited set of circumstances.
The phrases refer to the nullification of an unacceptable substance (the first, in a larger substance 60 times the amount, the second in general) intentionally.
Often, the presence of a forbidden substance can be nullified AFTER THE FACT if there is a halachic method, but one cannot go into a situation introducing a forbidden substance with the a priori intention of considering it nullified by invoking the a posteriori logic beforehand.
Some added sources courtesy of the Star-K
One may not mix even a small amount of non-kosher food into kosher food.23 This is known as “ain mevatlin issur l’chatchila.” Similarly, one may not put a small amount of milk into a very large pot of meat, even though the milk will be batel b’shishim. If one did this intentionally, he, his family, and the person for whom he is mevatel it may not eat it.24 However, if a gentile company adds a non-kosher ingredient and the non-kosher ingredient is batel, a kosher consumer may buy this product as there is no prohibition of “ain mevatlin” for the gentile.25 This is only true if it was not done explicitly for Yidden.
23 Y.D. 99:5
24 Y.D. 99:5 and Taz 98:10. See also Reb Akiva Eiger. In regards to selling it, see Rama & Taz 99:12.
25 See Darchei Teshuva 108:20. This is why a tablet is considered kosher even if it contains magnesium stearate, a possible non-kosher ingredient usually mixed into the product at less than one-sixtieth.
As previously indicated, Star-K will only certify products that are 100% kosher.