What is the clustered index on this table? If there is no clustered index - create one using both columns with CompanyId as the leading column.
If that cannot be done - then create a non-clustered index the same, with CompanyId first and SearchParts second.
Of course...if more of your queries only use SearchParts, for example - to get a list of companies with that part then using a covering non-clustered index with SearchParts as the first column - and CompanyId as the second column or as an included column.
Hashbytes will make an even wider column for than what you currently have for your SearchParts column and that means it'll be even slower.
Please post the complete CREATE TABLE code for the table including all indexes and constraints. Then post your code and an actual execution plan as a loadable execution plan that we can drill down into to see what's going on.
If you can't do that, then the best we can do is say that you've done something wrong and you need to keep trying.