This is a good question. Concerning VanitySearch if you use a passphase seed, a base key is generated and used to generate addresses up to reach the desired prefix (similar to BIP38 and BIP44 derivation paths), no PNRG is used. Trying to find the key would require to find the seed and to compute until the prefix is reached. That means that to find a private key you have to perform (in average) 'prefix difficulty' time 'number of possible seed' iterations, which is huge.
A tool such as john the ripper that generates password can beat weak passwords on system using fast password encryption algorithms (such as MD5) but in the case of vanity addresses, you need for each password to run up to the prefix difficulty. In other words, this is unfeasible.