Where can I find them? Even the vendor says they're there so I checked GECK and I did find it. However, I've been searching everywhere for them...

I think they show up after you've completed the BOS quests.
The sandstorm AFAICR doesn't show up either until you've made contact with them.

So I'd have to finish the ncr alliance with the BoS as well? I finished all the other BoS quests and I'm also a member...

Oh... Well then I don't really know.
The patrol appeared once for me as they left Hidden Valley towards north.
After that I never saw them again. :/

Well I guess I'll just wait there then.. Thanks.