Try to distinguish between need + object and need + verb.

Need + object is always a full verb, like 'want'.
e.g.
I need a drink. | The remote control needs new batteries. | You don't need lead to make gold. (Strange example, but this is where it belongs.) | I need glasses for reading.

Need + verb can also be a full verb. As a full verb it is usually followed by to-infinitive.
e.g.
He needs to see a doctor straightaway. | You need to let me know by Monday if you want to take part.
Fortunately I didn't need to pay for it. = I didn't have to pay for it. (i.e. I didn't pay) – but see 'I needn't have paid' below.

One exception to the 'need+to-infinitive' pattern is when 'need' is followed by –ing. This –ing verb has a passive meaning (same as want –ing).
e.g.
Does this shirt need ironing? = Does this shirt need to be ironed?
The plants need watering once a week. = The plants need to be watered…

Need is also a modal verb, like 'must': no –s in the third singular, no 'do' in questions and negatives, no past forms. And always followed by another verb (bare infinitive, i.e. infinitive without 'to'). In this respect, its main difference from 'must' is that we do not use it in affirmative sentences (unless with restrictive adverbs such as 'hardly' or 'only').
e.g.
We needn't stay long.
Need we leave so soon?
She's lazy, slow, and stubborn. Need I say more?
He need never find out what I said.
I need hardly remind you that this information is confidential.
We need only look at the building to see how much money it will take to repair.

Note its use with a perfect infinitive (i.e. have done sth):
I needn't have paid for it. (i.e. Unfortunately, I paid for it. Note the difference from "I didn't need to pay for it".)
[Most of the above examples taken from the Longman Dictionary of Contemporary English.]

The use of the modal in questions and negatives is more common in British English and a bit old-fashioned.
Whoever told you that "it is becoming more and more common to use 'do not need'" was referring to "needn't do" being replaced by "don't need to do" (though "don't have to do" is even more common).

Your second example (You don't need lead to make gold, i.e. need+noun) never created problems or doubts and has nothing to do with the modal 'need'.

Your first example (Noblemen need not pay taxes) is also fine. See this article entitled "Nobles need not pay taxes" (http://www.commondreams.org/views05/0201-23.htm) based on something written by Marc Bloch.
It would be equally correct to say "Noblemen do not need to pay taxes" but much more common to say "Noblemen do not have to pay taxes".