If you have "output value rounding" enabled, that can increase the fee by up to 100 sats.
I went through all the settings in Electrum but couldn't find anything out of the ordinary.
What version of the client were you running? Let me repeat it again,
it will not work on any released version. You need the linked PR - and - to be connected to a low-fee server.
You need both.
OR you can just run that one-liner in the console:
wallet.relayfee = (lambda: 0)
That in itself is sufficient.
My bad. I completely forgot about the bolded part in your post. I thought being connected to a server accepting sub 1 sat/vByte transactions would be enough. I tried it on version 4.6.0 and not the linked PR. I will give it another shot and make sure to enter that command in the console before I do.
Thanks!