Update: As of 2013-12-10, a hot fix has been released that resolves this issue. Related changelog:
Gaige's Interspersed Outburst no longer prevents critical hits from registering.
Before that hot fix, here's a workaround:
I found this post at the Steam forums that explains what may be the cause of the game not registering the headshot if playing as Gaige (My Kingdom for a Wand help | steamcommunity.com):
I had the same issue and had to respec because there's a bug with the Interspersed Outburst skill in the Little Big Trouble tree. The crits simply don't get registered and you're stuck shooting the orc in the face over and over again.
If you have a point in Interspersed Outburst, you might want to respec to remove that skill and finish that mission.
Also, try not to use elemental weapons or weapons with splash damage, to avoid the magical orc dying by elemental DoT or splash damage instead of the critical hit.