If it is "Un mesaj" (masculine), why is it "două mesaje" (feminine) and not "doi mesaje"?
It is. But in Romanian some nouns are neither masculine, nor feminine. They are neuter.
The neuter gender has the singular like a masculine noun, but the plural like a feminine noun.
Message (mesaj) is one of them.