How to delete files when the node that displayed them is deleted?
It's a revisions thing. I guess it makes sense. If you have revisions enabled for that content type, it keeps all your old files on the server (associated with old revisions), so replacing a file definitely is harder. If you try to remove it and add it again to the node, the name/link is updated, as I mentioned in my question. Since a file with that name is kept on the server and there is a name duplication, it adds those "_0", "_1" etc suffixes to future uploaded versions of that file's name.

I understand why this is happening though, since the whole point of revisioning is being able to revert to any past version of the page.

The work-around is that you can actually delete the old revision from the 'Revision' or 'Moderate' tab (if using Workbench Moderation) that contained the file you're trying to replace. Then upload it again, and the name should then match without you having to go back and edit any links pointing to that file.

Hope that makes sense and that it helps somebody else too!