I had a similar issue.

It looks like the electrum server I connected to was rebroadcasting the old transaction with the low fees.
I was able to double spend with a higher fee by connecting to a different electrum server which I guess has already removed the old transaction from the mempool.

To be on the safe side I used RBF this time. :-)