C'est dingue quand même. J'avais beau supprimer le marque-page de la barre d'outil de Firefox, de vider le cache, rien n'y faisait : le favicon de mon lien ne se mettait pas à jour! Solution:

sudo apt-get install sqlitebrowser

Fermer Firefox et ouvrir /home/user/.mozilla/firefox/XXXXXX.default-#####/places.sqlite avec sqlitebrowser

Chercher l'entrée du lien concerné dans la table "moz_favicons" (via l'onglet "Browse Data") puis l'outil de recherche, en sélectionnant la colonne "url".
Double-cliquer sur les entrées correspondantes et supprimer ensuite les valeurs.
Sauvegarder.

Maintenant Firefox chargera et affichera le nouveau favicon!

Voir également : http://www.opensearch.org/Specifications/OpenSearch/1.1

Pour convertir les favicons en base64 : http://www.motobit.com/util/base64-decoder-encoder.asp