You are right in than many easter eggs use hidden buttons on a single menu and require arrow selections to move between them. For example, from a particular button, using right, up, down in that sequence could go to the egg, but the buttons linked to from those arrows are hidden (and possible stacked one on top of the other).
Using a number press is slightly harder, but you should only need nine screens if you avoid zero. All you do is go to the screen that corresponds to the number selected on the handset and store a value in a GPRM and keep count of how many menus have been 'seen'. If you ensure that you multiply each selection by a factor each time, and keep a counter running on the selections made, you'll be able to check if the correct sequence was entered.
For example, multiply each value by 1, then 10, then 100, then 1000 and require a sequence of '3,4,2,1' would result in a value of 1,243 being stored in a GPRM. No other button sequence will give you this value, so if it is there then the correct sequence would have been entered.
Problems arise with this if you ask for a six figure date reference, as the maximum value you can store in a single variable is 65535. However, using more than one GPRM and checking each would easily get around this. For example, selection 1 goes into GPRM1, selection 2 into GPRM2 and so on. Use GPRM0 for the math needed to keep count and then have a series of logical statements in a script that checks the value in each GPRM in turn, such that if correct the egg can play, otherwise something else shows - main menu, track linked to last button selected, etc. Alternatively, use a smaller factor than ten, or some other construct that will give you a unique value.
Are you trying to do this on a 'normal' menu that the viewer ordinarily arrives at, or are they actively opting to go to a 'code entry' menu? If the former, your challenge is to know whether they are starting the sequence of date entry, or simply selecting the button to play the content it is linked to. It might be useful to use a combination of (at least) nine hidden buttons as the first on the menu and then the normal menu buttons in view (which actually are buttons ten and upwards). You could then set the egg up by the user firstly entering a button sequence of up, down, left (from any of the visible buttons to take them into the first of the hidden buttons), followed by a number entry sequence. This is a bit more complex for the user, but will mean you can use less menus.
If they go to a code entry menu, it's easier still, but also obvious there is an egg there to be found... at which point many people might not bother with the handset, but put the disc into a PC where their DVD player lists all tracks anyway.