How is it so difficult for such a large and supposedly competent organisation to publish and enforce to it's staff a simple two bullet policy that fixes all of this:

1) Published cabin baggage size and quantity limits to be enforced for everyone, regardless of travelling class or shininess of FF card. Have the bag cage next to the gate and physically check any bag that looks oversized. Gate check it if so.
2) If flight full and some cabin baggages requires checking in, start taking it from group 3 (4?) downwards.