EDIT 3:
Removed the normal maps posted because they are all wrong as WhiteNoise pointed out. I'm taking the bump mapping discussion to TIGS Forum and will only post pixel art for critiquing from here on.
EDIT 4:
Actually my normal maps wasn't wrong. There are several ways of creating normal maps and I'm using the technique Valve uses among others. My biggest problem is that I'm creating the normal maps from height/bump maps and that there is too much information lost when approximating the surface normal. But as I said I'm moving this technical discussion to TIGS.
EDIT 5:
Ok, WhiteNoise was right. The normal maps I posted were completely wrong. I feel really bad. Interesting enough they were fine internally, I just couldn't export them properly.
----
Here's the result of my latest bumpmapping experiment and it's obvious right now that the code I've got that translates depth maps to a normal maps is too crude.
This is perhaps most noticeable when looking at the blocks where you can see that there are stray pixels and the same is true for the characters.

If I'm going to do this I'll need full control so I'll have to pixel the normal maps by hand, or at least edit the normal maps.
ps. The guard was inspired by Camdogs henchmen.