Rotary Encoder with interrupts - erratic behaviour

Question

I'm trying to change my working rotary encoder code (stolen from here) to an interrupt-based code on my Mega2560. The trouble is that the result behaves very erratically, even though the physical setup is exactly the same as the working code. The determined encoder incrementation is jumping back and forth, when monotonically turning in one direction.

The interrupt-based code currently looks like this:

const long int baudrate = 115200;
const int debounceTime = 5;  // time in ms, in which the interrupt is not reacting. Starting at the first trigger of the switch.
const int clk1Pin = 19; // clkpin (signal A)
const int dt1Pin = 18; // dt pin (signal B)
const int sw1Pin = 4; // switchbutton pin
volatile int encoder1Val = 1500;  // what i want
volatile int firstSwitchTime = 0; // helper variable for debouncing
volatile int cnt = 0; // counters for debugging
volatile int cnt2 = 0;
volatile int cnt3 = 0;
volatile int cnt4 = 0;
volatile bool switchlock = false; // flags for debouncing and readout flow control
volatile bool readoutflag = false;
int cycletime;
void setup() {
// Set up pins
  pinMode(clk1Pin, INPUT_PULLUP);
  pinMode(dt1Pin, INPUT_PULLUP);
  pinMode(sw1Pin, INPUT_PULLUP);
  attachInterrupt(digitalPinToInterrupt(clk1Pin), encoder1Decoding, CHANGE);
Serial.begin(baudrate);
}
void loop() {
// only [print the data] and [release encoder1Val incrementing lock] after the debouncing period has passed
  cycletime = millis() - firstSwitchTime;
  if (cycletime > debounceTime) {
    readoutflag = true;
  }
if (readoutflag == true && switchlock == true) {
    switchlock = false;
    readoutflag = false;
    Serial.print(encoder1Val);
    Serial.print(",");
    Serial.print(cnt4); // Total amount of interrupt calls between readouts
    Serial.print(",");
    Serial.print(cnt); // Amount of effective interrupts
    Serial.print(",");
    Serial.print(cnt2); // Amount of "increment branch" calls
    Serial.print(",");
    Serial.print(cnt3); // Amount of "decrement branch" calls
    Serial.println();
    detachInterrupt(digitalPinToInterrupt(clk1Pin)); //ensure atomic action
    cnt = 0;
    cnt2 = 0;
    cnt3 = 0;
    cnt4 = 0;
    attachInterrupt(digitalPinToInterrupt(clk1Pin), encoder1Decoding, CHANGE);
  }
}
void encoder1Decoding() {
  cnt4++;
  // if outside of debounceTime: change encoder1Val
  if (switchlock == false) {
    switchlock = true;
    firstSwitchTime = millis(); // remember the first time, the interrupt changed in a bouncing group
    cnt++;
    // .. decoding encoder ..
    if (digitalRead(clk1Pin) == digitalRead(dt1Pin)) {
      encoder1Val++;
      cnt2++;
    } else {
      encoder1Val--;
      cnt3++;
    }
  }
}

It is relatively complicated for debugging reasons, as will become clear in a moment. When turning the encoder counter-clockwise, the resulting output is this:

Value, Total Interrupts, Effective Interrupts, Increment Branch, Decrement Branch:

1501,2,1,1,0
1500,33,2,0,2
1499,0,0,0,0
1500,1,1,1,0
1499,19,2,0,2
1498,24,0,0,0
1499,5,2,2,0
1500,0,0,0,0
1501,15,1,1,0
1500,16,2,1,1
1501,43,0,0,0
1500,3,1,0,1
1501,1,1,1,0
1502,6,1,1,0
1503,3,1,1,0
1504,2,1,1,0
1505,1,1,1,0

The values should increase monotonically. They don't, so what's happening?

1. The first readout makes sense: One successful interrupt call, one increment branch run, one value increase.
2. The second readout is already strange: two decrements, but only one less value?
3. The third is completely inexplicable: a decrement without the interrupt even being called.

I'm completely puzzled. Anybody got an idea where to start?

What I tried so far:

• Searching the web. Seems to be a new problem.
• Using the encoder without interrupts ("polling"). Works flawlessly, but is speed limited.
• Explicitly analyzed the bouncing period of this rotary encoder using interrupts. Worked flawlessly. Result is: BouncingTime is mostly less than 5ms (very few outliers).
• Plotted the data coming from clk and dt (x-ticks are 1ms, they're overlapping):

There is one bounce visible in the beginning, but the rest seems quite alright.

As I'm completely at a loss, any help is much appreciated!

Edit 2023-07-25:

The most important question is, why the ISR keeps on decrementing encoder1Val, even though i only turn in positive direction. This happens in all variants of the code. An absolutely stripped down version with the same behaviour can be found below:

void loop() {
  Serial.println(encoder1Val);
  delay(500);
}
void encoder1Decoding() {
if (millis() - firstSwitchTime > debounceTime) {
    firstSwitchTime = millis();
if (digitalRead(clk1Pin) == digitalRead(dt1Pin)) {
  encoder1Val++;

} else {
  encoder1Val--;

}

}
}

Result:

1500
1494
1497
1502
1513
1515
1518
1515
1516