Yes, adjusting and using the Unsupervised rule is your best bet to prevent this from continuing. My philosophy for deduplication is I would rather default to having extra duplicate contacts that I can clean up later than having two people become intertwined and, as you've experienced, can be rather sticky to separate.
There are a few ideas thrown around in the comments of this question: Dedupe Rule not working. (Full disclosure: I have an answer on that question). Lesley also has a great recipe in her initial comment to you up above.
Best write up about deduplication
The best free resource for Deduplication understanding and recipes is this blog post by spidersilk: Understanding CiviCRM Dedupe Rules. Section 6 is titled 'Some Recommended Rule Recipes' and section 11 is 'Tips for Setting up Effective Dedupe Rules'. The whole article is excellent, but for a tldr; those sections are great.
An Extension that could help
The No Overwrite extension can help with accidental over-writes in certain cases and might be worth installing. We have it installed on our CiviCRM setup.
How we do it
Lastly, just for another example, we have a lot of children in our organization being registered. A parent will often use his/her own email address to register a child, so we had to come up with a way that was more than just email. Our unsupervised rule is as follows:
First Name; Length - 4; Weight - 5.
Last Name; Length - blank; Weight - 5.
Birth Date; Length - blank; Weight - 10.
Email; Length - blank; Weight - 10.
Weight threshold - 20
This allows matching if the birth date and email address are the same (the only scenario this doesn't work is identical twins, and I'm okay with that risk). Also, if this is a normal adult registration (and adults normally don't provide their birth date), we can still have a match based on first four characters of the first name, the last name matching, and the email matching.
This catches a lot of duplicates, but certainly not all of them. Thomas Smith and Tom Smith with the same email address is probably going to be the same person, but our rule will not catch it. And I'm okay with that. Again, I'd rather have extra duplicate contacts than incorrectly intertwined contacts. As a matter of practice, every month or so we manually run General dedupe rules that are "Email only" or "First Name and Last Name" to catch the extra duplicates. Yes, it's manual work, but it's way easier to take the time for that than separating two people who were not in fact the same.