This is a known issue (pretty sure it was reported here on the forums, in fact) -- the FTP server doesn't trigger a media library update on deletions. This is not the intended behavior and will be fixed ASAP.
For a temporary workaround, updating the media library from the commandline is all that's needed to fix this. Or you can manually enter the URL to the old media library update page -- it's no longer linked to nor supported, but it's still there.