Apple - iOS available space doesn't add up

Is this device older than 2 years and has never been reset?

I can't tell you exactly what to do but this article quotes some possible solutions:

• Do you happen to send and receive a lot of messages with multimedia? that could be clogging up some of your storage especially if you set the settings to delete messages to never.

• How much space do you seen take by the Other category? Other may include:

  If you've ever connected your iPhone to iTunes, you're well aware of the "other" stuff taking up space on your device. This data contains things like Safari's browser cache, your email, Siri's cache, reminders, notes, stocks, weather data, emails (including attachments), text messages, iMessages (including images and videos), app data, etc.

  • Check voicemails?

  • Try to reset Safari Cache and data.

EDIT: OP indicated that the issue is indeed with the "Other" category, this article has some tips on how to try and locate and free up space taken by various elements that make up this category.Also check this Apple forums thread. Download any mentioned software there after doing your own DD.

Here's what "Other" includes, in full:

Browser cache

Mail cache

Mail messages

Mail attachments

Safari's Reading List

iTunes Backups

Crud resulting from jailbreaking your iDevice

Game data

Saved data files

Call history

Notes

Media

Voice memos

So, after a call with Apple support, they advised trying to take a backup and restore (after they suggested doing a "clear all settings", which failed). Problem was, over the weekend this happened again and I couldn't even take a backup as the phone kept disconnecting due to the space issue. Thankfully I took a backup last week which I was able to restore from.

Basically, the only way to solve this issue was to do a complete restore from a previous backup. Absolute joke really!