I got an email from Steam telling me that ClassiCube is now Steam Deck Verified.
That means a human at Valve played ClassiCube on a Steam Deck and checked all the boxes.
I find this interesting because the game doesn't have controller support or anything, but I guess the out-of-box Mouse/Keyboard Steam Input bindings did the trick.