http://tools.ietf.org/html/rfc3986#section-3.1
Scheme names consist of a sequence of characters beginning with a
letter and followed by any combination of letters, digits, plus
("+"), period ("."), or hyphen ("-"). Although schemes are case-
insensitive, the canonical form is lowercase and documents that
specify schemes must do so with lowercase letters. An implementation
should accept uppercase letters as equivalent to lowercase in scheme
names (e.g., allow "HTTP" as well as "http") for the sake of
robustness but should only produce lowercase scheme names for
consistency.

scheme = ALPHA *( ALPHA / DIGIT / "+" / "-" / "." )
Quindi, se inizia per una sequenza di lettere/numeri/+/-/. seguito da :// è potenzialmente un URI valido, altrimenti non lo è.
Puoi fare rapidamente la verifica usando una regex del tipo "^[a-z0-9\+-\.]+://" (in modalità case-insensitive).