The odds of someone 'randomly' generating the private key to that address is so small that you can effectively consider them lost forever. There is a chance that if quantum computing ever becomes reality that it might be possible to crack it, but I wouldn't hold my breath if I was you.
This scenario is precisely why HD wallets were developed... all addresses/keys can be recovered from the single seed... and generally, any backup will then be able to recreate any missing addresses/keys that were used after the backup was made.