Even with protected_hardlinks enabled you can still achieve pretty much the same effect with an open file descriptor via /proc/$PID/fd – the files in that directory appear as symlinks, but their behavior is really more akin to that of hardlinks (or dup(2)-ing an already-open file descriptor).

$ sudo cp -p /usr/bin/sudo /usr/bin/sudo-alt
Password: 
$ ls -l /usr/bin/sudo-alt
-rwsr-xr-x 1 root root 223760 Oct 30 11:19 /usr/bin/sudo-alt
$ exec {sudo}</usr/bin/sudo-alt 
$ sudo rm /usr/bin/sudo-alt
$ /proc/$$/fd/$sudo whoami
root

So if you really want to be sure nothing’s still got a way to execute an suid binary that’s been unlinked, a reboot might be the only way to be certain. (You could try to enumerate open file descriptors system-wide and kill processes that had potentially risky ones, but that seems prone to race conditions you could still lose.)

[Edit: hmm, I suppose perhaps truncating or overwriting the binary before unlinking it could also solve the problem without a reboot.]