Queueに指定した内容の要素が含まれているか調べるには、Containsメソッドを使います。

ただし、このメソッドではIEqualityComparerを指定できないため、Dictionaryのように大文字小文字の違いを無視して比較するといったことはできません。　そういった比較条件を指定した上で要素が含まれているかを調べるには、LINQの拡張メソッドContainsなどを使う必要があります。

Containsメソッドを使ってQueue内の要素の有無を調べる
Imports System
Imports System.Collections.Generic
Imports System.Linq

Class Sample
  Shared Sub Main()
    Dim q As New Queue(Of String)()

    ' Queueに要素をEnqueue
    q.Enqueue("Alice")
    q.Enqueue("Bob")
    q.Enqueue("Charlie")

    ' Queueに"CHARLIE"が含まれているか
    ' (大文字小文字の違いが意識されるため、"CHARLIE"は含まれないものとして扱われる)
    Console.WriteLine(q.Contains("CHARLIE"))

    ' Queueに"CHARLIE"が含まれているか
    ' (LINQのContainsメソッドを使い、大文字小文字の違いを無視して調べる)
    Console.WriteLine(q.Contains("CHARLIE", StringComparer.OrdinalIgnoreCase))
  End Sub
End Class
実行結果
False
True

文字列の比較オプション(StringComparer)については文字列と比較オプション・カルチャの並べ替え規則、IEqualityComparer<T>インターフェイスによる同値比較のカスタマイズについては等価性の定義と比較 §.IEqualityComparer, IEqualityComparer<T>を参照してください。