The version byte (like PUBKEY_ADDRESS) is prepended to the rest of the address data, and only certain values are allowed. You can't change it or add to it without making an address that's incompatible with everyone else's Bitcoin clients. So a mainline Bitcoin address can only start with 1 or 3, and if you want to influence the other characters, you have to do it via brute-force with vanitygen (or similar).
Vanitygen works by generating many addresses and checking them against the given pattern. There's no special trick to it. You can't predict or influence the characteristics of an address before completely generating it. (This is similar to Bitcoin's proof-of-work.)
By mass producing such addresses , one could actually "mark" that particular sequence to the point where it is easily recognized by users of BTC and customers.
Yeah, except that I can generate an address with the same "mark" as easily as you can, so training people to recognize your prefix actually makes phishing a lot easier.