list manipulation – AnyTrue is too good (compared to MemberQ)

One possibility for lists of integers is to use Clip:

iMemberQ(l_, s_) := s == Max @ Clip(l, {s, s}, {s-1, s-1})

For your examples:

L = Range(10^8);
iMemberQ(L, 1) //AbsoluteTiming
iMemberQ(L, 10^8) //AbsoluteTiming
iMemberQ(L, 10^9) //AbsoluteTiming

{0.729907, True}

{0.648677, True}

{0.631598, False}

L = RandomSample(Range(10^8));
iMemberQ(L, 1) //AbsoluteTiming
iMemberQ(L, 10^8) //AbsoluteTiming
iMemberQ(L, 10^9) //AbsoluteTiming  

{0.651394, True}

{0.616799, True}

{0.613475, False}

If you need to do membership tests for multiple elements with the same list, you could consider using Nearest (Nearest is a little slow, but only needs to be done once):

SeedRandom(1);
L = RandomSample @ Range(10^8);

nf = Nearest(Sort @ L); //AbsoluteTiming
nMemberQ(nf_, s_) := Length(nf(s, {1, 0})) > 0

nMemberQ(nf, 1) //AbsoluteTiming
nMemberQ(nf, 10^8) //AbsoluteTiming
nMemberQ(nf, -1) //AbsoluteTiming

{21.915, Null}

{0.000957, True}

{0.000041, True}

{0.000995, False}