I don't think people would remember them better if completely random. Rather, I think if they're completely random, people might correctly assume they can't, and remain appropriately skeptical; if they include a vanity prefix, people seem likely to remember the vanity prefix and somewhat less likely to pay attention to the rest.