An example from a few years ago: To find a random prime, the "correct" way is to generate a random number, and check if it's prime. However, for performance, people would instead generate a single random number, n, and then try n+1, n+2, etc. until they got a prime.
The result? Too many RSA keys used the same primes, because primes following "a long run of non primes" were much more likely to get picked than say the upper prime in a prime pair.
Once two RSA keys share a prime, you can use Euclid's algorithm to find out which. Get a large batch of badly generated RSA key pairs, and you were likely to find some collisions.
In conclusion it's not that looking for performance optimizations is inherently bad, but you really have to strictly prove that you don't change anything important.
The work I'm guessing you refer to on colliding prime factors is by Heninger et al., "Mining Your Ps and Qs", USENIX Security 2012 [1]. That paper does not mention anything about PRIMEINC causing this problem. The cases they found all related to bad entropy or extremely bad ways of generating moduli (like, pick two random values from a short list of known primes and use that as the modulus---an IBM product actually did this).
In fact, PRIMEINC is provably secure for generating RSA keys (though this was only shown somewhat recently): Abboud and Prest [2] analyze the distribution of outputs from PRIMEINC and show (see Section 4.1) that the security loss is negligible under quite mild conditions. Concretely, generating a reasonably sized RSA key using PRIMEINC rather than uniformly random primes reduces the security of RSA by a few bits at most.
But in some sense this reinforces your point---it was definitely not trivial to show that a tweak as seemingly simple as PRIMEINC is actually safe!
I remembered reading https://rjlipton.wpcomstaging.com/2012/03/01/do-gaps-between... which I suppose only says this _could_ be very bad.
Very interesting and great that it was resolved in the negative!
It's possible to choose p and q badly, even if you're choosing them randomly, so yes, it's always worth checking. Without the checks there is a chance, even if it's a small one, that your communications are completely insecure.
But in truth the answer is : It depends.
Always do the analysis, and understand the risks and trade-offs.
If the error probabilities are low enough, it's much more likely that your computation is invalidated by atmospheric radiation.
On the other hand, some of the code could be wrong, so I agree it's good to have an independent soundness check.
The article says the chances of a problem with independent randomization are approximately 1 in 2^500. Recall a UUID is 128 bits. Am I thinking right, this would be the odds of roughly duplicating UUIDs multiple times in a row?
At what limit is the additional code complexity warranted?