It seems in the last week or so, the Company search does not work in the Edit Contact screen. It used to be that you could type a word of a company name into the Company field and you would get a list of possible results to select from. This no longer happens.
Currently, in order to link a Contact with a Company, you have to enter the full company name 'exactly' into the Company field. The full company name is very difficult to find manually when there is a large number of Companies in the system. (It also seems that the Export Customer function does not include Companies that are not linked to any Contacts.