I think it’s actually the deactivated account that’s keeping the user from coming up in a search rather than a suspension. Try suspending the user, but activate him.
The suspension dialog allows for a custom reason:
You can also change the user’s email to some random address, like suspended123@no-email.invalid in case someone should try to reactivate it.