In what circumstances is it safe to automatically de-duplicate contacts?
As soon as you automatically "merge", it will never be 100% safe. If you want to be sure, never dedupe (ie put dedupe rules that are not possible to match) and ask your users to login.

Obviously, it means that you will end up with tons of duplicates, so in practice, you will need to relax the rules and accept that you might have two different persons that end up merged in the same contact. This isn't as bad as it sounds, and it happens with every shared list of items that several people can update, and it doesn't create too much problems.

So your choice is what type of error you want to avoid more: having more duplicates or having more incorrect merges. For what I've experienced, the most relaxed rule is to consider that everyone sharing an address is the same person, and the strictest want the first and last name and email and country.

you might want to add an extra layer of protection if you send emails with the hash token (so your contacts don't have to login and are automatically identified) so they can't change their name by accident with this extension https://civicrm.org/extensions/no-overwrite

And you could enable the detailed logging http://book.civicrm.org/user/advanced-configuration/logging/ so you keep the history of all the changes if you haven't done it already