Well since the old one was not working right the obvious answer is to ask yourself, is the fan working? You can also simply remove the keyboard to look at the fan, if it is a new one it should be clean. Another thing you should do is always ask for the old parts back when you have a computer worked on, they are your property after all. This makes it harder for the shop to claim they did work that was not performed.
there is no real easy way of checking whether the fan is replaced or not, since there is no unique serial number to identify the part that you can track.
But you can take keyboard off and check to see if the fan vane has any dusts on it or not. Old fan will have some dust particle stuck to the surface even when they are cleaned, new one will have a waxy clean vane surface.
May this year, be the year of 'DO'!
I am a volunteer, and not a paid staff of Lenovo or Microsoft