Uploaded avatars are stored in your data/avatars directory within the Xenforo install, there are subdirectories for each size of avatar generated from the original. They are further subdivided into directories based on the user's ID.
<xenforo_install_dir>/data/avatars/<size_code>/<prefix>/<user_id>.jpg
The size code will be: h, l, m, o, s with the o being the original. The prefix is the thousands part of the user ID, so a user with an ID of 5 would have a prefix of 0, one with an ID of 3456 would be 3, etc.
If a user deletes the avatar via the dialog in their profile then then the XF server will delete the files from disk.
So unless you periodically backup your filesystem in some way, such as periodic copies or the filesystem has some kind of automatic snapshotting setup and have one from before they deleted the avatar then I'm afraid the file is gone and you won't be able to recover it. If you don't have any backups you could I suppose check to see if the Internet Archive happened to duplicate a copy if they have scraped your site recently, worth it at a pinch.