Well, I kept searching a bit and found a lot of interesting threads from samsung owners seeing this exact same behaviour after flashing a CM Rom.
I "might" have found a fix. Apparently, you need to fully charge your phone, then remove the battery long enough for a specific chip to be unpowered and to reset itself. That is, supposedly, the only way to force a battery recalibration on some samsung phones (I found threads from S2s and S4s owners).
Charging right now (with phone turned off), so I'll let you know tomorrow morning how it went.
Cheers !
And of course, if hat doesn't help then I'll just buy a new battery.