If you don't have the AD Recycle Bin enabled, you won't be able to find deleted objects.
If $user is expected to an exact match, you should also be using the -eq operator, not -like. If you want a fuzzy match, -like is correct but you should surround $user with * like so: *${user}*.
If $user is supposed to be the logon name, and not the friendly name of the user, then Name isn't the correct property to filter on, you will want to check against SamAccountName, not Name:
Get-ADObject -Filter "SamAccountName -eq '$user'"
If you are only interested in user objects, and not other AD object types, consider using
Get-ADUser in lieu of Get-ADObject. The syntax for what you specified above is the same, but will guarantee you only get ADUser objects, not ADComputer, ADGroup, etc.
Also, you should avoid using -Properties * and -Filter { ScriptBlock } arguments when using the AD cmdlets. Only use the Properties you need to process later, and use a string based filter like so:
Get-ADObject -Filter "Name -like '*$user*'"
See my answer here for best practices when using the -Filter parameter with AD cmdlets (also explains why not to use -Properties *), and this answer here for more details on why you should not use ScriptBlock parameters for AD filters.