Is it possible for phones on different networks (ie Vodafone and O2) to connect to one BES server?

Yep. I think most companies do that.
BES doesn't care.

it would be suicide by RIM if they didnt' do that.

It doesnt matter what carrier or where the carrier is located (US or abroad) as long as the devices are on the same BES server or assigned to a BES in a multi BES server domain that share a common BES database.

BES won't discriminate, I've had Sprint/Nextel, T-Mobile, Verizon and Cingular (AT&T) on the same BES.

Should make a sticky about this?

Cheers guys. Thought that would probably be the case but some companies would do anything to be able to charge for another license so though that i would ask.

No, too small of a fact for an entire sticky ...I think it'd be better if there were a list of 10 really common but simple questions, like this one that came up to put into a sticky ... hey, why don't you put one together!