The gemara in Gitin 54b declares worthless a Torah scroll that had all the Tetragrammatons rewritten because it ends up looking menumar (spotted), apparently because this would be a violation of "ze eili v'anvehu - the verse associated with the concept of beautification of mitzvot (hidur). My understanding is (was?) that hiddur is not generally necessary in order to fulfill the mitzvah. Why is this Torah then worthless?
There seems to be an issue with menumar which is worse than regular Hiddur, unrelated to a Sefer Torah.
Look in Suka 33a-b that if there are lots of berries on your Hadas - and they are spread in 2 or 3 spots - then it's menumar and it's pasul because it's missing its hiddur.
So we see that menumar is almost the opposite of hiddur and makes it ugly - and hence Passul.
A similar thought is expressed in the Chavrusa to Menachot 29b:
אמר רב כהנא: משום דמיחזי שנראה הספר תורה כמנומר! כשכותב ומוסיף בין השיטין את מה שחיסר. אבל ביתירות אין גרידת האותיות מכערת את הספר כל כך, ואינו נראה כמנומר.
When you make it menumar it's a lot uglier than if you erase words or squeeze them between the lines.
Once something is that ugly, be it a Sefer Torah or a haddas, it's not fit for divine use.
The Sde Tsufim in Gitin 20A has citted Chidushey Hatam Sofer in Gittin and in the Citted Gemoro succa 29B
I want to copy the text in hebrew and translate in english
דאפילו אם ואנוהו בשארי מצוות לאו דאורייתא, מכל מקום בכתיבת השם הוא דאורייתא כי כן משמע "זה קלי" השם הקדוש, "ואנוהו"
The litteral sense of the verse is bounded to the G-d, i.e. the Name of G-d. And the Tsivui is anvehu.
There is a lot of difficulties in this subject but I think that this Hatham Sofer is a big novelty and answer the core of the question.
The Rabeynu Krashkash (in Chidushey Haritba Mossad Harav Kook, I, page 175) says a wonderfull thing, the expression Ein HaShem min Hamuvchar is a paraphrase of the verse Ze Keli veanvehu
And now disappear an other difficulty.
Following the superficial reading, Eino min hamuvhar says that it is not mitsva min hamuvchar, but it is Kosher. How can Rav Chisda saying "Banu le machlokess" (so it is Passul)!?
Now, the following text of the Gemoro makes sense as a precise explanation of the term Eino min hamuvhar as a Psul of unaesthetic writing of the name of G-d!
an important detail enabling to diminish the contrast between the opinion of Rabbi Yehuda and the Chachamim
The Gemoro in daf 54B shows that The disagreement between Chachomim and Rabbi Yehudo no longer has to be held in case all the names were rewritten. So in menumar it is universally admitted that there is a psul of Ze Keli... (as Danny has added a further evidence from the Gemara Menachoss).
Rashi in Sukah 29b states that the requirement for hadar in arba minim comes from the passuk of zeh keili ve'anveihu.
Various rishonim (see tosafos there) ask on Rashi that zeh keili ve'anveihu is le'chatchilah, not be'dieved.
It seems from Rashi that when the absolute minimum expectation of hiddur is lost the din of zeh keili becomes an ikuv.
It is a 'dead' mitzva.