There are already great answers, and I for one would simply ask him again.
But I also have an additional way of re-retrieving the name if you don't want to ask him directly: Find something that might interest/entertain him on the internet. Then ask him for his mail address, because you'd like to send him something interesting. Depending on the topic, you may first start a conversation about that topic and then tell him you have an interesting/funny thing to show him and ask for his contact details. Alternatively, you can ask for a chat account or similar, if your company manages something like that.
Of course, you are out of luck if your company mail addresses do not include the full name, but you would know that from your own beforehand to decide if this approach can work for you.
Also, first you might think about whether he may have already sent you a mail. In that case it's easy, just dig out that mail and hopefully you have his name.
Also, our company has a floor plan at the entrance and each room has pictures and names at the door - maybe you have something similar and overlooked it so far?
There are also two very culture depending options I've seen (also dependent on your character):
- If he shares an office with you, ask your colleagues if you can take a picture with them - as you like to collect them / show your family who you work with, then print it out and have them sign it.
- If he doesn't share an office and you don't have a floor plan, simply draw one yourself and let it go around - ask your colleagues to fill it out, each with their own name. That way you get all the names and they may even pick up the idea and ask you to hang it in the floor somewhere so all new guys have the benefit of it.