I think these discussions of "tricks" tend not to be productive, because we mean different things by the word, and also because it tends to have negative connotations, but some of us aren't using it negatively.
Suppose we talk instead about "mechanics" -- aspects of the way the game behaves. We assume the player knows (from the original tutorial levels, or NeoLemmix tutorial levels, or reading the manual) a basic one-line description of what each skill does, e.g. bashers go horizontally forwards through terrain and remove it. Now, consider the following three levels:
(1) You have only two bashers, but there are three pillars in the straight path between hatch and exit. You have to find an alternative way around that only passes through two chunks of terrain.
(2) You have to utilise the fact that lemmings turn round in the basher tunnel while it's in progress, but not after it's complete.
(3) You have to utilise the fact that bashers can move upwards on a sloped terrain–steel boundary.
In mobius's classification, (1) is a logical puzzle and (2) and (3) are both tricks, but I think (2) is actually very different from (3). (2) requires a leap of imagination or lateral thinking; (3) requires the player to discover a new game mechanic.
I think levels involving new game mechanics are the ones where we need to be careful to play fair. It's very frustrating to spend ages stuck on a puzzle because you assumed it could be solved using only the mechanics you already know, and then to ask for a hint and find out that it depended on a mechanic you didn't know. Puzzles of type (2), though, can be really satisfying to solve, because it feels great to have that creative leap or moment of insight. The example I always point to for this is "Attack of the Subconscious" (an Insane Steve Cheapo level), but there are plenty of others.