Actually, it's hinted at in vanilla. The gravyard guardians and so on... Rumours on Malta. But I expect it's a small minority of outcasts who regard nomads as some sort of god-like-thingy. Also, I would expect the Outcasts from vanilla (at the point at which you come into contact with the OC at elast) to be largely ignorant of the blue man group, only having fleeting and vaguely mysterious contact with them around what used to be the Unknown jumphole.
Personally, I've always played my OC characters to have a respect for nomads, but not worship them... It's sensible to have respect for bears when you're in their woods. But they're not gods.
As for Order/OC relations, I think the main contributing factor to their current hostility is the Order's past alliance with the corsairs.