Apple - delete all backups of all machines and reset time machine drive

Just wipe the drive clean using Disk Utility and then have Time Machine start it all over again. I'm not sure what kind of issues you are going to run into because I've done that probably 50 times in my life and never had an issue besides falling asleep while I wait for an entire Time Machine backup to finish.

Disk Utility would be the best tool. But if you want to do it manually...

rm -rf doesn't work, even with sudo (fs denies permissions)

This is the only way to go:

sudo tmutil delete [path to machine name]

Example:

sudo tmutil delete /Volumes/BackupDisk/Backups.backupdb/oldmachine

Just use that command for every machine you want to delete. It will delete every backup for that machine.