There are some rules on the formation of nouns. The word "Mtembeza" doesn't seem to fit these rules, as it ends with an "-A". When we are dealing with a noun derived from a verb, and the noun is also in the M-/WA- class (1/2), we see the following possibilities: 1. Noun ending in "-I", we place "M-/WA-" in front of the verbal root and change the final vowel "-a" into an "-i", e.g. "mlinzi", "mzazi". 2. Noun ending in "-JI", we place "M-/WA-" in front of the verbal root and add the suffix "-ji" at the end of the radical, e.g. "mchezaji", "mwuzaji". 3. Noun ending in "-U", we place "M-/WA-" in front of the verbal root and change the final vowel into "-U" (actually a bit more complicated than that), e.g. "mwaminifu", "mwangavu". 4. Noun ending in "-E", we place "M-/WA-" in front of the verbal root and change the final vowel "-a" into an "-e", e.g. "mtume".
I've replied to your other comment, but just to increase visibility of it, mtembeza watalii is absolutely fine. This is a common way to form compound nouns from a verb + object. You simply detatch the ku- from the verb phrase and add the right noun class prefix, and you can then write the two words together, separately or with a hyphen.
kutembeza watalii → mtembeza watalii
kufanya kazi → mfanyakazi
There are more examples in my other reply.
No, a lot of compounds derived from a verb and its object just have a noun prefix added directly verb stem which is then not modified. The object is placed afterwards, either written together as one word, separate, or attached with a hyphen, without much consistency (don't pay too much attention to whether I've written the examples below together or apart). It's much less common as just a derivation of the verb, although that does happen too, but it mainly happens with compounds. So mtembeza watalii is absolutely fine, but just mtembeza is not used.
Other examples of this process:
mfanyakazi = worker (from kufanya kazi)
mfanyabiashara = business(wo)man, trader (from kufanya biashara)
mtema kuni (or mtemakuni) = woodcutter (from kutema kuni "to cut firewood")
msema kweli (or msemakweli) = honest person (from kusema kweli "to say the truth")
mpiga piano = pianist (from kupiga piano "to play piano")
mpiga-mbizi = diver (from kupiga mbizi "to dive")
mpigapicha = photographer (from kupiga picha "to take a picture")
mpitanjia = passer-by (from kupita njia "to pass the way")
kifyonzavumbi = vacuum cleaner (from kufyonza vumbi "to suck dust")
Some verb-only derivations:
muumba = creator (from kuumba "to create") mlipwa = payee (from kulipwa "to be paid") mfiwa = mourner, bereaved person (from kufiwa which is kind of like "to be died on")
This process can also be used to form adjectives such as:
mume wangu mpendwa "my beloved husband"
msichana mchapa kazi "a hard-working girl"
mwalimu mwalikwa "a guest teacher" (literally "invited teacher").