I didn't noticed the restart at the same level... they all look a bit the same :-P. Maybe show some text when they start with the level name?
Nokia 3410 had
Munkiki's Castles preinstalled which took advantage of the phone's 3D rendering functionality (it was software rendering really, just implemented by the phone instead of doing it in Java). I do not remember any other 3D game for these phones although a very simple maze would be possible.
A few years after the game i mention above (~2006 according to timestamps... time sure flies fast) i made an attempt for an FPS on mobiles (where the S would stand for stabber :-P although you'd also cast fireballs). I managed to make a fast renderer, considering the phone's abilities (i remember that the rendering was too smooth for the 3510's screen to keep up as it had very slow response times and everything became a blurry mess the moment you moved the camera):
It used everyone's favorite 3d method for blocky mazes: raycasting. TBH these days i think rasterization would probably be faster, especially with a preprocessed map and would also allow for non-rectangular rooms (ala Doom, although without elevation differences), but it would require way more work on the tool side (and i do not think i even considered at the time).
I also, apparently, managed to make a royal mess of the build process. The above are two of the available configurations, the "high end" at the first two images and the "low end" (even using different assets) at the last image. Since it would be impossible to use the exact code everywhere (for example the Nokia Series 40 phones were faster with 16bit framebuffers whereas the Series 60 used 32bit framebuffers) i wrote a custom preprocessor and build system specifically for J2ME (which i only used for this project). It provided some C-like preprocessor functionality, but it also "knew" about mobile models and their characteristics, SDK locations, resource locations, etc. But all that stuff only worked on the machine i had at the time, i just tried to compile some code and it blew up with tons of errors :-P.
Mobile development was a PITA at the time, i remember i was working on another game (a small top down racing game) and i had on my desk every Java phone i could get my hands on and any emulator i could find... and constantly had bugs coming from the people i was cooperating with (who would handle distribution, etc to different carriers). Sun made a mess with J2ME by allowing third party VMs and having practically zero tests. I eventually gave up when i started getting bugs for phone models whose official emulators would show no issues. Not much later i met someone on IRC whose job was in a company dedicated to testing J2ME games and he told me they basically had a small warehouse of different phones just for testing - which pretty much confirmed my view on how bad things were. As sucky the controls are on Android, you can get stuff working on it with little issues and i find amusing when i read some developers online complaining about the fragmentation on Android :-P.