It's nice to see innovation even in it's smallest form. And it does still exist somewhere. Just seems to be darn hard finding because the games don't get that much publicity and thus not many stores get them.
Games like Oddworld Abe's oddysee and Battle zone for the PC both showed some odd twist to the dime a bucket games. They had different gameplay than the other games. Though they might be built on gameplay already known it's combined uniquely making them somewhat interesting.
Problem is if you want truly innovative you'd get a problem. There are only a limited number of control devices present. The keyboard/joystick can be used to move an object either with rules such as gravity, or without rules such as shoot em ups. Both in 2D and 3D. The mouse presents a mouse pointer, but there's also limits to what you can do with that thing. Lemmings was about assigning attributes. The incredible machine was about placing stuff. Oxyd and (I think it could be played with that) Marble madness was funny ways to move stuff. Now you're almost back to square one again. To get a truly innovative thing you have to think of some control method hitherto not thought of. Without more control devices and with some consumers and many producers going with the tried and true method it won't be easy to spot a truly innovative game since noone'd be talking about them.