Almacenamiento del favicon - ¿Qué carpeta se debe usar?

Solo lo guardaría en la carpeta del tema si esperara que el favicon cambie al cambiar el tema. Lo cual no hago.

Un favicon es parte de la identidad total del sitio, no una función del CMS. ¿Qué pasa si usas software que no es WP para diferentes partes del sitio, como una galería de fotos, foro o wiki (o todos los anteriores)?

Coloca el favicon en la raíz del sitio web, y todos los paquetes de software tendrán acceso a él, generalmente de forma automática (aunque puede que tengas que eliminar los enlaces LINK codificados manualmente de los temas individuales).

(Edición) Para aclarar: Si no se especifica un LINK, todos los navegadores web modernos (excepto Seamonkey, aunque existe una opción para habilitarlo) buscan automáticamente un favicon en el directorio raíz, es decir, ejemplo.com/favicon.ico. Por lo tanto, no hay razón para agregar un elemento LINK, y hay buenas razones para no hacerlo.

Además, si el elemento LINK está mal formado (tiene un error tipográfico, por ejemplo) o el archivo ubicado allí está corrupto o en un formato que el navegador no entiende, el navegador buscará /favicon.ico de todos modos, por lo que no tener un archivo allí generará errores 404 en tus registros.

Hay un caso en el que un LINK es apropiado, y es si deseas diferentes favicons para diferentes páginas de tu sitio.

Debe estar siempre en la carpeta raíz para que funcione tanto si enlazas explícitamente a él como si no.

También puedes usar esta función en el archivo functions.php de tu tema para enlazarlo explícitamente:

function my_favicon() {
    echo '<link rel="shortcut icon" href="' . get_bloginfo('wpurl') . '/favicon.ico" />';    
}
add_action('wp_head', 'my_favicon');

Aunque ya hay respuestas de calidad aquí, pensé en aportar mi perspectiva desde un ángulo diferente. Administro muchos blogs y sitios en un entorno WordPress MultiSite, donde el directorio raíz no es una opción. En estos casos, lo mejor es colocar los favicons en el directorio del tema como recomienda el WordPress Codex.

El Favicon no es dinámico y no "entra en conflicto" con nada más, con eso en mente, lo codifico directamente en el header.php y así queda resuelto.