Short answer to your question: RFC 1035 says,
NS records cause both the usual additional section processing to locate
a type A record, and, when used in a referral, a special search of the
zone in which they reside for glue information.
...the additional records section contains RRs
which relate to the query, but are not strictly answers for the
question.
...When composing a response, RRs which are to be inserted in the
additional section, but duplicate RRs in the answer or authority
sections, may be omitted from the additional section.
So the bottom line in my opinion is that, yes, if the response does not contain the A record matching the NS record it some section, something is likely misconfigured somewhere. But, as the old dodge goes, "be liberal in what you accept;" if you are going to make the queries, you will need to handle situations like this. DNS is awash in these kinds of problems.
The longer answer requires a question: how are you getting the original DNS server where you are starting the MX lookup?
What you are doing is a non-recursive query: if the first server you query does not know the answer, it points you at another server that is "closer" in the DNS hierarchy to the domain you are looking for, and you have to make the subsequent queries to find the MX record. If you are starting your query at one of the root servers, I think you will have to follow the NS pointers yourself like you are.
However, if the starting DNS server is configured in your application (i.e. a manual configuration item or via DHCP), then you should be able to make a recursive request, using the Recusion Desired flag, which will push the repeated lookup off onto the configured DNS server. In that case you would just get the MX record value in your first response. On the other hand, recursive queries are optional, and your local DNS server may not support them (which would be bizarre since, historically, many client libraries relied on recursive lookups).
In any case, I would personally like to thank you for looking MX records. I have had to deal with systems that wanted to send mail but could not do the DNS lookups, and the number and variety of bizarre and unpleasant hacks they have used has left me with emotional scars.