Alex,
I believe that this cannot be configured on CUCM - I heard that it can be done by modifiying some special file on CUCM, but obivoulsy this will make your CUCM installation us.
However, in our 2Ring IPPS (IP Phone Services), you can set the order of search fields - so you can set the last name field to be first. Also, we have an advanced search in IPPS, that we call IntelliSearch. If you have this on, then every first letter entered is associated with all the letters under the given button, so when you are search for "Richard" you only need to hit 3 keys, while with a standard search, you would have this many hits to enter the first three leters: 3+3+3.. You can request a free trial here: http://www.2Ring.com/newjuice
Michal