I will be applying for MS in Computer Science in the United States and I want to ask for a letter of recommendation from one of my professors, with whom I share a strong relationship. He has left the university and won't be able to write the letter with the university's letterhead. He will have to send it from his personal email ID, since his official email ID has been deactivated. Will this put a dent on the authenticity of the letter? Are the admission committee members willing to contact my professor in case of any doubt or discrepancy?
If he is still prepared to write you a reference then he will.
He can state that you were a student when he was teaching at X institution and that will be accepted.
If the admission committee feels it is necessary to contact him then they will do so.
I have sent reference letters to the Academic secretary and she printed them on letter headed paper - this was while I was on holiday in a different country and the student needed the reference quickly (comes down to planning ie 5 p's: proper planning prevents poor performance...)