A sharepoint list item is deleted from list as well as all recycle bins. How'd an administrator know when this item was removed and who removed it?
Is it possible at all?
Best way to do this is use the OOTB auditing features or use an event reciever to record the deletion somewhere using code.
http://msdn.microsoft.com/en-us/library/bb397403(v=office.12).aspx
Yes, it is possible. Enable audit logging on site collection level.
http://www.sharepointedutech.com/2011/02/14/setting-up-audit-logging-in-sharepoint-2010/
The quick and easy answer is to turn on audit logging, but I would caution you to carefully consider how you leverage that feature. It can cause considerable bloat in your content databases and IMO should be used as sparingly as possible.
If you're only concerned with deletion then I could encourage you to only enable the "Deleting or restoring items" items option and not be tempted to turn on the rest.
...and given that you're concerned with deleted/purged items, make sure that you're holding on to that audit information long enough for it to be useful...i.e. don't trim the log after 30 days.
If you have list or library, you can simply setup an alert. There are a lot of settings like "new items are added, existing was modified" or "items are deleted" and e-mail can be sended in minutes. (setting says immediately, but it depends on job settings).
Great site for alerts is here http://sharepointalert.info/2009/09/getting-started-with-sharepoint-alerts/