After User Profiles are imported from AD , first thing is to make these profiles available for search. Check your Content Source and ensure that the mysite host is included as both:
http://mysite.company.com and sps3://mysite.company.com , else your profiles will
not be indexed. Run a full crawl after this.

If you are getting this error on crawling
"Access is denied. Verify that either the Default Content Access Account has access
to this repository, or add a crawl rule to crawl this repository."

Do one of the below
Creating a crawling rule with other Account Information solves the Problem.
OR
Follow these steps:
1.Click Start, click Run, type regedit, and then click OK.
2.In Registry Editor, locate and then click the following registry key: HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Lsa
3.Right-click Lsa, point to New, and then click DWORD Value.
4.Type DisableLoopbackCheck, and then press ENTER.
5.Right-click DisableLoopbackCheck, and then click Modify.
6.In the Value data box, type 1, and then click OK.
7.Quit Registry Editor, and then restart your computer.


Source: http://support.microsoft.com/kb/896861

Next in you VS project ... you will want to add web reference to the webservice.
If you not able to add the web-reference and get the following error...

The document at the url http://mysspurl/_vti_bin/Search.asmx was not recognized as a known document type.
The error message from each known type may help you fix the problem:
- Report from http://mysspurl/_vti_bin/Search.asmx' is 'The document format is not recognized (the content type is 'text/html; charset=utf-8').'.
- Report from 'DISCO Document' is 'Root element is missing.'.
- Report from 'WSDL Document' is 'The document format is not recognized (the content type is 'text/html; charset=utf-8').'.
- Report from 'XML Schema' is 'The document format is not recognized (the content type is 'text/html; charset=utf-8').'.


In this case you need to use the full URL to your Sharepoint site. For example,
http://mysspurl/sites/mysite/_vti_bin/Search.asmx. When you've received the list of
services, click on "Service Description". This will change the URL to
http://mysspurl/sites/mysite/_vti_bin/Search.asmx?WDSL. You'll now be able to add the
service.

Assuming that the web-reference name you set is 'PeopleSearch' Sample code:

PeopleSearch.QueryService queryPeople = new PeopleSearch.QueryService();
queryPeople.Url = "http://mysite.company.com/sites/mysite/_vti_bin/search.asmx";
queryPeople.PreAuthenticate = true;
queryPeople.Credentials = new System.Net.NetworkCredential(strUserName, strPassword, strDomain);


StringBuilder query = new StringBuilder();
query.Append("");
query.Append("");
query.Append("");
query.Append("");
query.Append("urn:Microsoft.Search.Response.Document.Document");
query.Append("");
query.Append("");
query.Append("");
query.Append("SELECT ");
query.Append("Accountname, ");
query.Append("preferredname, ");
query.Append("FirstName, ");
query.Append("LastName, ");
query.Append("WorkEmail ");
query.Append("FROM SCOPE() ");
query.Append("WHERE ");
query.Append("(\"DAV:contentclass\" = 'urn:content-class:SPSPeople') ");
query.Append(" AND (\"preferredname\" LIKE '%" + "deployment" + "%')");
query.Append(" OR (\"FirstName\" LIKE '%" + "deployment" + "%')");
query.Append(" OR (\"LastName\" LIKE '%" + "deployment" + "%')");
query.Append(" OR (\"WorkEmail\" LIKE '%" + "deployment" + "%')");
query.Append("");
query.Append("");
query.Append("11000");
query.Append("");
query.Append("");

ds = queryPeople.QueryEx(query.ToString());

make sure .. the URL does not include '?wsdl' else it will give this error.. {"Possible SOAP version mismatch: Envelope namespace http://schemas.xmlsoap.org/wsdl/ was unexpected. Expecting http://schemas.xmlsoap.org/soap/envelope/."}