Drupal - Why does the favicon sometimes not show up and generate "page not found" errors, and other times does show up

Some browsers search for favicon under http://example.com/favicon.ico without checking. But they are minority now.

Most respect:

<link rel="icon" href="http://example.com/img/icon.png">

as described by W3C.

If your site tries to use <link> approach but fails on some pages, like admin pages rendered using different template, and you do not have favicon.ico in default location, you will get exactly described effects.

If browser is looking for http://example.com/favicon.ico when you have proper <link rel="shortcut icon"> it is a browser problem, not yours. It means browser (or at least that part of it's code) is outdated, unless it looked under correct URI first and got another error, but then you would see two errors in log, one for right place, second for outdated one. In Mozilla's queue there is a number of reports about improper favicon detection by FireFox - in example this one. It shows how even modern browsers can sometimes fall back to old methods.

Quick and easy fix for this pain, is to use the Redirect module and make a redirect for it.

Once the module is enabled, go to admin/config/search/redirect/add and use favicon.ico under from and to should be the actual location of your theme's favicon.ico.