iPhone "Other" storage still present after Erase All Content and Settings

The problem here is you are adding data to the phone after you restore it. Get a clean restore (no need for holding any keys down like DFU or other items) since this is purely about erasing the filesystem and then not adding any apps or accounts.

Then you’ll know the actual usable storage and be able to decide if you need service due to storage being marked unusable or if you just restore data from backup / cloud to take up that space.

Is there a "deeper" wipe than ‘Erase All Content and Settings’ available? Yes, in fact there are two. A restore from Recovery mode. Slightly deeper is a restore from DFU mode, but it's unlikely to be better in this case.

To restore from Recovery mode:

With the phone connected to a computer with the latest iTunes:

1. Press the Power and Home buttons and hold them until the phone is switched off.

2. Release the Power button and keep holding the Home button till the phone enters the Restore mode.

3. Click Restore (not Update) for a "deeper" wipe. This is not the same as a standard restore.

Other thoughts:Deactivate iPhone Drive? (Source: https://apple.stackexchange.com/a/323032/33389 ) But you say you "have not signed into anything", so it should already be inactive. Delete all accounts, if any. Finally, a WAG: It could be due to an extraordinary amount of bad flash that Apple has marked as unavailable.

I understand you haven't installed a single app, but the list shows Self Service, the client side app to a mobile-device-management solution. This is not part of iOS and is a separately installed app. MDM lets the administrator place any files on your iPhone, so it is possible that the space is consumed by data provided through MDM. You can contact your administrator.