They are probably still in the program. But your customised settings do
not show the relative/absolute icon. Here is a way to get it back:

Start your macro recording, so you can get the menu displayed.
Right-click on the menu, and select "Customise". Find the Macro menu,
and find the Relative/Absolute icon. Drag it to the Macro menu, and you
should be ok from there on. Let us know how it goes.

I couldn't find the Relative/Absolute icon anywhere in any of the
'customize' dialogue box tabs. (xl2003)
You could try resetting the toolbar:
Tools>Customize>Toolbars. Scroll down and find the Stop Recording
Toolbar.Click on it and "Reset".
Otherwise this single line in a macro might do it:

Application.CommandBars("Stop Recording").Controls.Add Type:= _
msoControlButton, ID:=896

(you could just execute this line once in the Immediate window of the
Visual Basic Editor instead (Ctrl+G to get the Immediate Window
visible in the VBE)).

This does bring up the stop recording toolbar but it still will not
record using relative  references. I tired both ways of doing it and
it still does only absolute  references.

You're sure you're not seing the likes of:
ActiveCell.Offset(6, 3).Range("A1").Select

which in absolute  refs would be something like:
Range("F12").Select?

What sort of action are you recording?

No menu displays when I do this.

now I know where to do it as
well.