あれ? こちらで試してみた限りでは、-1 にはなりませんでした。

Dim s As String = "Square" & vbCrLf & "Enix"

Dim i As Integer = s.IndexOf(vbCrLf)

MsgBox(i, vbSystemModal)

本当に vbCrLf が含まれていない、という可能性はありませんか?

> どうすれば検索できるのでしょうか。 
Regex や InStr など、幾つかの方法があります。
http://rucio.cloudapp.net/ThreadDetail.aspx?ThreadId=9722