I would actually imagine signing a NAP followed by an Alliance might override the NAP since the later is basically a stronger version of the same thing. It really would not surprise me if that caused the NAP to end.
The tribute system is pathetic too.
I'll always accept free money, but what's the point of a one time tribute payment of 25 (or less) gildar? It's barely worth my time, and doesn't motivate me not to attack the AI.
The real tribute is that they give you 10% of their income every turn for 30 turns. The up front bonus is just a sweetener.