Regardless of other answers, I found this bash solution some time ago:
defaults read /Library/Preferences/com.apple.preferences.accounts deletedUsers
Gives one account name for every user removed from the system, in this format. It doesn't matter how long ago it was removed as long as the com.apple.preferences.accounts.plist file itself is not tampered with:
(
{
date = 9999-99-99 00:00:00 -0000;
"dsAttrTypeStandard:RealName" = "Account name";
"dsAttrTypeStandard:UniqueID" = 501;
name = deletedusername;
},
{
date = 9999-99-99 00:00:00 -0000;
"dsAttrTypeStandard:RealName" = "Another name";
"dsAttrTypeStandard:UniqueID" = 502;
name = deletedothername;
}
)