I know you aren't happy about using the NVarchar datatype on the table columns but still I have this question. If you converted the varchar in the table to be nvarchar to match the parameter coming in from the Unicode ORM framework would it have caused a seek, solving the problem, and negating the need to change coallation settings on the DB/Server.
It's so much fun to watch someone else assume the issue to be the lowest level, index/data corruption type issue, and finally work their way back up to 30,000 feet and find the issue right outside the window. I wonder if the Guru DBAs would have started with coallation? Gosh, I hope not.