cache formatting not working I already had problem where my phone was turning on for a while, showing 'apps are optimizing' and 'no storage left'. I had fixed it previously using recovery mode and wiped cache partition. Everything worked perfectly straight away.

However this time I tried already wiping cache partition in the same way about 10 times already and I also tried to manually delete all content of /cache using adb and su, with no success.

Is there anything I could do to fix it?

If this can help, my phone is Nexus 4, running rooted 5.1.1 lollipop.
If you are familiar with fastboot, you could boot or flash TWRP and format the cache that way.

Download the current TWRP img file, copy it to your fastboot folder, and issue the command

fastboot boot twrp-3.0.2-0-mako.img 

Once it loads and starts at the main menu, select Wipes and then untick everything except Cache and Dalvik cache and execute the wipe and reboot. 

If that fails, it might be time to flash a new factory image.