(Updated 2004-11-11: Pointed out all-or-none matching constraint that applies here. If you read this post, please also read the follow-on thread started by hv for more regexp-probing fun.)

(Updated: Added quotation for context; added conclusion.)

Regarding:

And try as I might, I can't find a string that behaves differently between the two. I've tried all the possibilities I can think of, like sadad salalad saladad slad sal, but they behave identically. I still have a nagging doubt that there may be a difference; if anyone can point it out I be most appreciative.

There's no difference because we can prove that the regular expressions are equivalent for any atomic regexes x and y (when constrained to all-or-none matching, which is the case in the original poster's question):

(x|y)? === (x?|y) === (x|y?)

The proof goes as follows. (Note: I use (x) instead of
(?:x) to denote grouping.)

We start with (x|y)?

We can rewrite as (x|y)|E because, by definition, r? is equivalent to r|E where E matches the empty string.

We can rewrite as x|(y|E) because regex union | is associative.

And rewrite as x|(y?), again by definition of ?

And as x|(y?|0) because the regex that never matches anything – 0 – is the identity for union.

And as (x|y?)|0 by associativity.

And finally as (x|y?), again, because 0 is the identity for union.

(The proof for the (x?|y) case follows immediately from regex union being commutative.)

To use your example, let x = (?:al) and y = (?:pre) and the same proof applies. That's why you can't find a string that matches s(?:al|pre)?ad differently than s(?:(?:al)?|pre)ad – there isn't one.

Sometimes it's easier to go after the proof than the counterexample. : )