Do I need to take special steps to fully restore an iPhone after jailbreaking it? I heard that the iPhone has some sort of counter that counts every unauthorized connect or something like that, and with said counter, Apple Geniuses can tell if it has been jailbroken and they won't fix it. I was also told that when you perform a restore on the iPhone, the counter is saved so anyone can tell if it's been jailbroken even after restore.

Is there a way to fully restore the iPhone and leave no "fingerprints" behind ?
This is the first I hear about this so-called "counter". I don't believe in such and I'm pretty sure when you restore an iPhone using DFU modus, the iPhone is completely wiped clean.   

As a matter of facts, I've jailbroken all my iPhones so far and passed by the Apple Genius bar several times. Once I even forgot to restore the device when asking a Genius for help. And he just smiled at me and said "jailbreak, right? What's your favorite app?" :)

So, no. I don't think there is such a counter and you're safe with a DFU Full restore.