Evade is an NPC-exclusive avoidance mechanic. It is triggered when an attacking mob is unable to reach its target (due to terrain limitations for example), or when the mob is leashing (running back to its original location after having chased a player on a too long distance, for example). Its purpose is to discourage exploitation of terrain versus an enemy. When a mob is in evade mode, it becomes immune to any and all attacks and spells from every player, and will regenerate health as though it was out of combat.
In the case of evade due to terrain limitations, the target should go closer to the mob so he becomes attackable again. The mob will then drop evade mode. This is often experienced in boss encounters, such as Onyxia and Anub'Rekhan.
Evade is also triggered by targets who have been trapped in the game field. These such creatures would walk into an area that cannot be exited, such as between two rocks. In this situation the target can still aggro, but it cannot be attacked at range. The player must be in melee range of the creature to attack it with anything.
Sometimes mobs spawn in tricky locations where it is hard or impossible to actually attack them without triggering evade. Such mobs are called "evadebugged".