I have tried using Kindlegen as well, it retains the underline on the links just like Calibre (unless I am missing something).
The <mbp:nu> tag works as expected for me with kindlegen.
<p><a href="whatever.html"><mbp:nu>Link text</a></p>
Creates a link with no underline. Just verified it with kindlegen 1.2 build 33307