Should HMAC or NMAC or plain Keccak be used for a secure MAC?
HMAC and NMAC make assumptions of the underlying hash function $H$ for their security proofs. Additionally they are designed to eliminate known flaws in other MAC constructions using MD type hashes.

NMAC is not $H(k1$ $||$ $H(k2$ $||$ $m))$, it actually uses the keys as the initial hash values, which require a higher level of access to the internals of the hash, meaning a large variety of implementations cannot use NMAC the same way they can use HMAC.

In response to your questions..


For HMAC, when the key length is shorter than the block length, there is no exploitable impact on security due to padding with null bytes. The maximum security will be the output length of $H$ or the input length of $k$, whichever is shorter.
NMAC is considered the stronger MAC, but because it requires modification of the initial hash value, it is less used in practice. Attacks on NMAC are applicable to HMAC, but not always the other way around. I would be concerned that there may be choices of IV that weaken $H$ with respect to it being a PRF, which could invalidate the security claims, however resistance against forgery in that case is most likely not compromised; this is only the case if the compression function is weak, and in that case there are other security issues with the hash.
Once again, since NMAC modifies the IV, you cannot have keys larger than the output length of $H$ for MD type hash functions. In HMAC, a key larger than the block size is hashed down to the output size, so the maximum effective size of the key is smaller.
Keccak can be used with HMAC but not NMAC, since the sponge construction security claim requires the state to be 0, and NMAC requires the state to be the key. The keyed sponge function $H(k$ $||$ $m)$ is likely more secure than HMAC for a given key length, due to the inner state being larger than the output length.


HMAC padding to the block size essentially allows a single iteration over that part of the message space to change the IV, making it closer to NMAC, since the next input to the compression function is the message. For HMAC, you will get the maximum security if the key length is equal to the blocklength, assuming that more security than the output length of $H$ can be achieved. The padding constants are there so the IV of both the inner and outer hash function are unique, but still related to $k$.

Keyed sponge functions gain security from capacity, with the bound being $min(2^{c-1}/M$ $,$ $2^k)$, where $c$ is the capacity, unless $M$ exceeds $2^{c/2}$. This means more security over large messages with a large enough capacity, since the security of HMAC starts to drop with every subsequent input block (correct me if I am wrong on that one), and is upper bound by $2^{c/2}$, where c is the digest size. This implies that a keyed sponge function can have a smaller capacity than is required for the security proof of HMAC, making it either more efficient or more secure given appropriate choice of $c$.

As fgrieu pointed out, HMAC and NMAC were not from NSA or NIST, but rather university research. The fact that NIST endorses it does not imply there is a weakness. The internal hash chain size is our limiting security factor here, as well as HMAC being constructed to make use of a hash function without limitation.