Do I really need to bring things in for a name change? Usually people checking references contact the company, ask if the person did work there and ask about their performance.
I've never heard or seen of anyone wanting to see paperwork as proof that the person worked there. Usually a verbal affirmation that the person did work there is good enough. At least, this is what I've always seen done and have done myself.
Also, I've never heard of someone who changed their surname due to marriage ever doing this.