Maybe it's a sentence about some kind of list, or some kind of database. I believe "We do not have his name in the database" makes sense. At least «У нас в ба́зе да́нных нет е́го и́мени» definitely makes sense in Russian.
Can it mean "we don't kniw his name" -- like, "Автор книги жил в Москве. У нас нет его имени"?
No, it sounds unnatural. In your context, «Мы не знаем его имени» sounds much better. (Alternatively, «Его имя до нас не дошло» works too.)
what about "we don't have the same name as him"--"нашего папы зовут Борис, а у нас нет его имени"?
No, this is not something we'd say in Russian.
I'd say «На́шего па́пу зову́т Бори́с, а нас зову́т по-друго́му».
Well in the United States we have "He did not leave his name," which sounds just as strange if you really think of it.
A valid context would be making a list of people for a meeting .... the Director of Marketing for XYZ Corp., "We do not have his name."
Why имени instead of зовут? Would they be interchangeable in this context?
I think зовут is a verv, whereas имени is a noun. Thus I suppose that you can't just substitute one word for the other, but maybe you could rephrase the question.
"There are also a group of several irregular "different-declension nouns" (Russian: разносклоня́емые существи́тельные), consisting of a few neuter nouns ending in -мя (e.g. вре́мя "time") and one masculine noun путь "way". However, these nouns and their forms have sufficient similarity with feminine third declension nouns that some scholars such as Litnevskaya consider them to be non-feminine forms of this declension" https://en.m.wikipedia.org/wiki/Russian_declension