no soy lingüista, pero si el repetir dos veces old quiere dar idea de que son amigos de hace mucho tiempo, se puede optar por
1) decir muy viejo, como propones
o
2) usar una palabra que contenga esa idea, a mi se me ocurre, por ejemplo "antiguo amigo", "viejo amigo"...
creo que Reed en ocasiones se refiere a la cosa como "viejo amigo", o al menos así me suena haberlo leido en las BM, y quizás sea una traducción al old, old friend
es que "muy viejo", asi, sin contexto, me suena repetitivo, como nieve blanca