Short answer is no, long answer however would be yes it's possible but requires a bit of work.
1. It is possible to track by encoding images. This is pretty much a virus and will be blocked by today's OS security patchs and the anti-virus.
2. Anything deleted isn't actually removed until overwritten and can possibly be recovered by 'undelete' software.
3. Google can find all indexed - if you know how to use it correctly. Using 'Advance Google Image Search' allows you to locate pictures easily from shape, size, part of the filename, description, format, colors, etc. It goes as far as face detection, photo content, line drawing or clipart, etc.