Here's what I found:
Recording/Creating a macro also creates a Code Module to hold the macro.
Deleting the macro later does NOT delete the module that contained it, and the presence of any modules (even 'empty' ones) will trigger the macro
warning.
To fix: press Alt-11 to bring up the VB Editor. In the Project Explorer sub-window (View>Project Explorer if its not visible), find your
workbook/project in the tree and expand the section under it labeled "Modules". Right click on any modules and select "Remove...." (when
prompted, don't bother saving/exporting it). When all modules are deleted the "Modules" section will no longer appear in the Explorer tree under your workbook. (If you have any add-ins loaded, leave those Projects alone).
If all you did was record macros or create them via the regular Excel interface, deleting modules like this should remove any remaining traces and
stop the macro warning.
If the warning continues, then you have forms or
VBA code behind a worksheet itself