Check your AD user  properties.......

but I am more interested in finding the cause.

We have verified AD user  properties are just fine.

Just a hunch, but check the domain  membership of the workstation that the user
is logged in at when the user  is added. I suspect that the only time  it shows
up without the domain\ prefix is when the user is automatically logged in from a
workstation in the same domain as the SharePoint server. Otherwise SharePoint
recognizes that the user is not in its default domain and places the domain name
prefix on the user name.

but the problem is that domain  name\user name
persist in SharePoint, takes over the display name property and used for all
references.

We have around 500 users  on the portal and around 15 had this problem. I made a
small program to update display names of these users (using SPUser object ) and
since then it is working fine.

If AD properties were the issue, this should have re-occur after a full
profile import.

Recently some new hires were added to the AD and one of them has reported this
problem.

I wasn't saying that it was the way it was listed in AD that was the problem.
I was suggesting that it had to do with the way the person who was adding the
user to SharePoint was logged in. As a later reply stated it probably does have
something to do with whether the person adding the user  was logged in to a
machine that had the SharePoint site in the Trusted Sites zone or not. When the
person is added to SharePoint a record is created. This is NOT the profile
record, that is created separately. When the person is added to SharePoint it
will generate a Display name for them in the People and Groups table. If that
gets created wrong then it needs to be fixed manually (your program is one
solution). Its not the AD properties, it's the way the person is being added
to SharePoint, or something about the workstation of the person who is doing the
adding.

If users  have added the Sharepoint to the Trusted SItes, the name will appear as
it is listed in AD: First Last, Last First, Etc.

If users have not done this and logged in through the login prompt then the
login will show  as domain\user