Error: "ERROR_NO_RESULTS_FOUND" when you use Search.asmx with FullText SQL query

I have encountered this bug that really irritated me today.
I was using Search.asmx with FullText SQL query to get some results and then display them to users using XSL through JavaScript using jQuery.

SELECT LastName,Company,AccountName,UserProfile_GUID, JobTitle,Size, Rank, Path, Title, Description, Write FROM SCOPE() WHERE ("DAV:contentclass"='urn:content-class:SPSPeople') AND (LastName LIKE 'C%')

worked

whereas

SELECT LastName,Company,AccountName,UserProfile_GUID, JobTitle,Size, Rank, Path, Title, Description, Write FROM SCOPE() WHERE ("DAV:contentclass"='urn:content-class:SPSPeople') AND (Company LIKE 'C%') 

did not work and it threw an error "ERROR_NO_RESULTS_FOUND"

After many trials and errors and a bit of research, it turned out to be a Microsoft bug.

"like statement will only work on a string shorter than 64 characters, above that it will fail gracefully leaving you with unexpected results..
"

The work around for my problem was to use CONTAINS as opposed to LIKE.
Please notice that the "company Name" is actually embedded within single quotes as '"Company Name"'.
Otherwise the Search service does not understand that it needs to look for the whole phrase.

SELECT LastName,Company,AccountName,UserProfile_GUID, JobTitle,Size, Rank, Path, Title, Description, Write FROM SCOPE() WHERE ("DAV:contentclass"='urn:content-class:SPSPeople') AND (CONTAINS(Company,'"Company Name"'))

Ref: http://social.microsoft.com/Forums/en-US/Offtopic/thread/12ea7757-7ca7-42b8-9ed2-59acd00d283d