Font info is also stored here:
- Stored table tags or in a deleted table title
- In a left/right master page, if your document is single sided and you had deleted the master page of the other side
- Master pages
- Reference pages
- Graphics files
You can also open the MIF file (preferably with MIFBrowse: http://www.grahamwideman.com/gw/tech/framemaker/mifbrowse.htm or in another text editor) and search for the font name.
Or you can deactivate "Remember missing font names" in the Preferences and then open your file. FrameMaker will permanently replace Palatino with another font. Only if the font is used by a graphics file, FrameMaker will still try to find this font.