Public Key in Use Verification
You have pretty much answered your own question.
Yes, such a check would be possible, but it would have a cost (need a database lookup, at least). That cost isn't worth it, because the risk of actually finding an address that has been created by someone else before is so utterly mindbogglingly small - it just won't ever happen.
Furthermore, even if such a check would be done, it would have severe limitations:

Only full nodes (which have access to their own unspent coin list) could do it directly; other wallets would need to query another service, which is inherently a privacy risk.
Hardware wallets are obviously unable to do this at all, as by definition they cannot access the internet.
Even on full nodes, generally no by-address index exists of the unspent coins list; only a list optimized for access by created-by-txid. Since it's an unspent coins list, it cannot account for addresses that were used in the past but don't currently have any coins assigned to them.
Even ignoring all that, such a check can only account for addresses that have actually been used. There are probably far more addresses created (and thus someone already has the key for) than have ever been sent to.