Re: What mess is going on in the transactions ?

https://bitcoinfees.21.co/#delay says the fee you used was 10x too low. If you want to avoid problems use a fee of .0005 routinely.

I wouldnt suggest any fixed fee. The transaction may also be unusually large (in byte) for Erkallys which might be why they didnt have this problem before. You either have a wallet that can make a good suggestion or you have to rely on 3rd party estimates from e.g. 21.co.

I use Electrum, and that's what it automatically put as fee for me. Each time it put me this, each time it worked well, so I did not changed anything.

The default fee for Electrum is 0.5 mBTC/kB. The fee you included in your transaction is 1/10th that. I suspect you may have changed it at some point.

This time I did nothing. Some long time ago I chose it manually, and I chose that. It seems that Electrum remembered my choice. What is more intriguing is that I recently performed a factory reset on my computer and just imported my seed into Electrum without touching to anything.