Information:
A new Orc introduced this week (May 21st, 2001). He shoots arrows, teleports, hides, then heals when hurt and reappears to attack you when healed up. They are tough and you should not take them lightly.
I found my first ones today east of Cove. They are said to spawn outside of towns. On Siege they spawn East of the Papua Bank.

How to kill:
If solo, Energy Bolt them, then watch for the double flash of a teleport spell. Cast reveal on the 2nd Teleport graphic (not the spot they were just at) and finish him off at will. If with another mage friend, one mana dumps while the other keeps it revealed.

Thanks to Watts for this information. Yes, even he PvMs every know and again.

Loot:
100ish gold, around 50 arrows, a bow, and a chance at a special bow.