I understand that "Il ne mange rien" is the correct order of words...

I talked to a native speaker and cleared this up. "Il n'a rien mangé" is the only correct form. Similarly "Il ne m'a rien dit" is correct, whereas "il ne m'a dit rien" is infact incorrect and sometimes heard being used by small children. I hope that clears this up.

-- Chris (not a native speaker).

I have heard the sentence "Il ne m'a dit rien du tout" said by a native French speaker. It set off bells in my head because, just as yourself, I learned to say "Il ne m'a rien dit". Apparently "Il ne m'a rien dit" emphasises that he really told nothing at all. Emphasis by inversion? Apprently it is possible. -- Chris (not a native speaker)

Bonjour Diana, One point of emphasis is that there is a very large gap between written French and spoken French. I learned that the negation using le passé composé is in the form: noun + ne + auxiliary verb + negation, i.e. pas, rien, etc. + past participle. While le passé composé is the conversational past preferred, I do believe the correct syntax is like noted above.