Solution to INSTALL_FAILED_INSUFFICIENT_STORAGE on Android

Since upgrading to KitKat I often face the problem which prevents me of installing or updating my apps:

INSTALL_FAILED_INSUFFICIENT_STORAGE

This error may occur even when there is more than 400 MB free on internal memory of my phone.

Here is how I cope with it. I clear the cache of media via ADB:

adb shell pm clear com.android.providers.media

Notice: negative effect will be loss of thumbnails, ringtone, etc..