Te rog trimite query-ul cu probleme.
Folosesti COLLATE? Prefixezi search string-ul cu N? Ce tip de date are coloana in care cauti? etc, etc...:)
Ce inseamna "aceleasi setari"? Clientul se conecteaza la serverul tau?
Vezi si BOL ---> Collation precedence.