If anyone has solved this issue I'd love to hear it.
Typical hotlink protection in htaccess
rewritecond %{HTTP_REFERER} !^$
rewritecond %{HTTP_REFERER} !^http://(www\.)?example\.com [NC]
rewriterule \.(gif|jpe?g|png)$ - [NC,F]
The result: Search engines show a self hosted version of your image instead of your hotlinked image.
The problem: A visitors browser remembers not being allowed to view the image so if they view the site directly at a later date the image remains hidden. This is not a caching issue, if you have properly set browser cache control to cache images then the browser remembers the error.
Condition: This only happens if a visitor clicks on the "Full Sized image" link or the "Website For This Image" link in the sidebar. It does not happen if they click on the x in the corner of the image shown by Google.
If anyone has solved this issue I'd love to hear it. If you'd like to test it remember that you need to clear your cache before visiting Google otherwise your browser will remember the image and show it properly which is not what a new visitor will experience.
Ideas on how to solve this or why it only happens when the visitor clicks the links and not the x beside the image?