When ADSI binding fails, can the program know that is the userid that is not valid rather than the password is not match? Will doing a lookup to the lists of user take too much time?
It depends on how many objects are in your forest/domain. Searches are efficient if you use indexed attributes.

When changing password using ADSI, will the program know that the password actually not meeting the complexity requirement?
you'll get 800708c5 error.

Try C:\>net helpmsg 2245