Unexpected Implicit conversion in a procedure
It was all down to collation of the column. It was different from the database's (and the table's) collation. Now changed the column's collation to database's and no more implicit conversion shows up. Have no idea about the internals and why it caused the problem.