Jeremy Orem de Mozilla comparte una solución alternativa con la cual no tengamos que instalar SQLite o siquiera cerrar Firefox. Todo es de ejecutar el siguiente comando desde la Consola de Errores (Menú Herramientas >> Consola de Errores):

Components.classes["@mozilla.org/browser/nav-history-service;1"].getService(Components.interfaces.nsPIPlacesDatabase).DBConnection.executeSimpleSQL("VACUUM");

Tan solo hay que copiar este comando y pegarlo en la ventana de la Consola de Errores y presionar el botón de Evaluar (no hay un aviso de cuando termina, pero se supone que Firefox quedará unos segundos colgado en lo que se ejecuta):

Consola de Errores / Firefox

Esto solo afectará a places.sqlite, no al resto de bases de datos, pero de todos modos solo places.sqlite es la que se fragmenta más.

Si no quieren estar recordando este comando, pueden instalar la extensión (experimental) Vacuum Places Improved, que agregará un botón en la barra de estado después de X inicios, o procederá automáticamente a desfragmetar la base de datos después de otros tantos inicios de Firefox.

De parte de Mozilla aún siguen discutiendo sobre si deberían agregar esto a Firefox y cada cuanto tiempo ejecutarlo automáticamente.