You would really have to kill the menu off when you switch to 'fullscreen'.
Use the Win32 API SetClassLong with the GCL_MENUNAME flag set to NULL to do this and to restore it when you return to 'windowed' you replace the 'NULL' with the menu resource identifier, eg:
and to restore it:
where CWndMFCClass is a ptr to your CWnd (or derived) object and MenuID is the resource name of the menu (use MAKEINTRESOURCE if the menu id is a numeric rather than string value).
You may prefer to use the :: scope resolution operator with SetClassLong.
Alternatively you can unregister the window class and re-register it without a menu but I don't know how much of a hassle this is in mfc. It's certainly a little more hassle in win32 than using SetClassLong to switch the menu on/off, so to speak.
Hope that helps some.
edit: Corrected hideous error - very sorry about that.