You will have to manually find files, which probably was what deluser would do.

Please note --remove-all-files is not the same as rm -r /home/user. The latter only removes the homedir (which may include files not owned by that user, although not usual), the former removes all files owned by that user from the system. At least if the manpage is to be trusted.

GNU find has a -user test, so you can do find / -user xxx to find all files owned by user xxx. xxx would be the user name, and can (and in this case will have to, as the user no longer exists) be the user's numeric ID. find also has a -delete option, so

find / -user xxx -delete

Should do it, although I've not tested the command with all the options at the same time.

EDIT: Numeric ID: The reason why I said you have to use a numeric ID is because, as you already deleted the user, his entry in /etc/passwd was deleted (it had, along with other stuff, the user ID, along with his username).

So, if you didn't remove his homedir, one of the easiest ways is to just query for the ID of the owner of that homedir:

stat -c %u /home/user/

(stat is a tool to read filesystem data. -c %u tells stat how to write its output, here I'm asking it to simply output the user ID)

If you like one-liners, you can even chain both commands:

find / -user $(stat -c %u /home/user/) -delete

(Of course you may prefer to run it first with no -delete to make sure there's nothing you want to keep, and to catch any mistake you've made writing the rest of the command. Mistakes when doing recursive deletion operations on / are not for the faint of heart.)