After all it seems like the fonts licensing restrictions isn't allowing embedding (Publisher was a lot clearer on that matter).
Hopefully it is possible to bye some kind of upgrade to allow embedding.

Stupid that it is so cryptic written in the fonts properties about if the font can be embedded or not!

As far as my testing goes (Word 2007 and 2016) I have found two things about embedding fonts in Word:

1. The font must be licensed for embedding, which is hardly ever the case for commercial fonts. Only font files which have property 'Font embaddability' with value 'Editable' or 'Installable' can be embedded. You may find the font's properties via >Control Panel >Fonts.
2. Fonts can only be embedded in DOCUMENTS, not in templates! So this feature is only available for docx and docm, bur not for dotx or dotm.