I've narrowed the query to this:
select * FROM items where accountid=4755 and (itemId like N'%9976%' or [description] like N'%9976%' or fulldescription like N'%9976%' )
Both 'Description' and 'FullDescription' have been scaled down from nvarchar(max) to nvarchar(4000).
Seems that still I cannot build index on that because it is too big (can't go any lower). Also, if I remove either 'Description' or 'FullDescription' it works fast, so the slowness is the compound effect. Also, this query without the LIKE conditions contains only 1,000 rows in a relatively small database.
We did end up with something similar to what Amir suggested here.. Since 98% of the data is pretty short we've created another two columns nvarchar(450) which meets the 900 bytes limit, then created indexes for them.
We're hosted on Azure and time is pressing, so we didn't look into free text search. We also came across Azure Search service which may be a fit for this, but that requires a time consuming POC.