Don't directly edit the database - this will cause nothing but pain and make
your SP installation unsupported.

The correct way to do this is to remove the users  at the site collection level
for each site collection they had access to, then run three (3) re-indexes for
search. After the 3rd the user should no longer appear