Candidates loaded through HDL not searchable using labels

I have loaded candidates using HDL along with the labels. When we search those candidates loaded through HDL using name or candidate number search is returning them. But when we use the label associated to them they are NOT being returned in the search result.

For the same candidates loaded through HDL if I delete the label associated to them which was loaded using HDL and assign the same label back using UI label search is returning them in the search result.

"Maintain Candidates and Job Requisitions for Search" process is already running and is scheduled to run every 15 mins.