Yes, they are the same species. Moench put it as different genus (Majorana), but still keeping references to Linnaeus' Origanum majorana.
So they are the same species, and both are acceptable (and valid) names, but the currently accepted name is Origanum majorana.
I use the Plant List: http://www.theplantlist.org/tpl1.1/record/kew-143853
This database is created by major taxonomic/botanical institutions. It is automatically generated from the most important taxonomic literature. IPNI (just google it) has much more names, it doesn't try to find the actual "accepted name", and there is a lot of double entries. Also this is done by Kew (and includes major database). BTW Plant List uses also IPNI as source.
Often different authors use different names (but list the original all synonyms), because they think that the such plant need to be in a different genus. So often such synonyms are easy to find and to agree. But in particular on subspecies and variety level, many people describe the "same" plant [with different herbaria sample]. To find synonym in this case it much more difficult, and people cannot really agree, if the variation are enough for a new variety, or just normal variation.
On the link of Origanum majorana that I copied above, you can see that most of the names are valid. One Invalid and two illegitimate. Invalid: it is not permitted (on botanical names) to have specific epithet similar to the genus. Illegitimate: probably they are published later (when a valid name were already available, using the same classification (in this case, the same Genus)).