Since upgrading to CCM 4.2(3) we are not able to search by first name from our IP phone directory. We can, however, search by last name and extension. I have looked at the xmldirectory.asp file but cannot determine if something has changed.
The Basic User search utility searches the first name, last name, and user ID fields for matches of any substring that you enter as search criteria. http://www.cisco.com/en/US/products/sw/voicesw/ps556/products_administration_guide_chapter09186a00801ecfcc.html
Any changes in the ASP file can result in a different behavior.
On the global directory search page leave the search field blank
Maybe you forgot to populate the First name while adding the users (maybe through BAT).
And I don't think it complains, as First name is not a mandatory field