The issue not because Euler angles can't represent all orientations (they can) but because they don't interpolate between two orientations cleanly. The analogy with the physical gimbal lock isn't 100% accurate, as your question accurately indicates, but arises due to the condition (the system is in a near-singularity state due to one of the axes being at 90 degrees). I'll try to give an example that link up how the physical and virtual models work.
Imagine being in a game in a standard FPS view where the mouse controls heading (horizontal rotation) and pitch (up/down rotation), and you are looking nearly straight up, facing north. Now, no matter how high you move the mouse, you can't actually "do a backflip" to look behind you without rotating your body 180 degrees around the heading axis (and also 180 around the roll axis (the barrel-roll axis), since your "backflip" view is upside down compared to just turning around).
Another way to think of the problem in the FPS: the game picks your roll orientation so that the top of your monitor is pointing upwards (so you're not leaning to one side). When you are facing directly up, there is no roll orientation that allows your "view up vector" to be anything other than horizontal, and mathematically you'd divide by zero if you tried to calculate the up vector from this orientation.
Now, imagine being in that same situation in a flight sim and a joystick. You're facing nearly vertical and want to "backflip" over the vertical point. Obviously the equivalent movement in the plane is to just slightly pull down on the joystick, involving none of the huge 180-degree flipping that the FPS game required. If the plane simulator simply interpolated Euler coordinates over the coordinate singularity, you'd see the plane spazz out and do some crazy 180-degree rotation between the two points. If the plane moved over the perfectly vertical mark, you'd get the same "division-by-zero" problem that we encountered in the FPS as it tried to figure out what angle to spazz through.
The equivalent analogy with the physical gymbal is if the rings are all aligned. Now, imagine trying to rotate the inner ring against the outer ring. There simply isn't a way to do it. that is gimbal lock. if all the rings are just barely unaligned though, and you try to rotate the inner ring's past the "zero mark" on the outer ring, you'd be able to rotate it, but you'd see the two inner rings do a quick 180-degree flip, just as we noticed in the FPS example when we wanted to "do the backflip".