Curious:
What type of file is this that you have the link in? Illustrator.eps or Illustrator.ai?
And what are you doing when you get the error, and what are your options in the error window, and how do you respond?
If it is an Illustrator.eps then all placed files are embedded, even if they were only linked to begin with.
When opening an Illustrator.eps file that was saved from an Illustrator.ai with linked Photoshop.eps images, Illustrator would still ask for a path to the original link, even though it was embedded by the save to EPS... and in that missing link dialog you were given the options of:
Replacing (which you can't do if you don't have the link anymore
Ignore and Cancel which seem to do the same thing... link comes up with a question mark in the links palette.
Extracting the placed image, which does just that but does so without making a preview, to get that back you have to open the extracted image in Photoshop and resave it, then update in Illy.
None of the methods above produce a screen image of the missing link when you first open the file, so I wonder what you did. Unless of course this no screen image behavior is different in more recent versions of Illy... I tested at home in v8.
So for linked Photoshop.eps files they are emdedded into Illustrator.eps files but only embedded for the purposes of placing the file into a layout and printing. If you reopen the same Illustrator.eps that prints fine from your layout, Illy looks to find the link and maintain it as a linked file in the links palette.
The odd thing is, if you place a Photoshop TIFF file linked, save the Illustrator as EPS, and close, then delete the Tiff file that you had linked, Illustrator does NOT report the link missing but opens the file without a hitch, and you will see your places image in the links palette as an embedded image.
So that means linked tiff files get "really embedded" when you save as AI.eps, instead of "kind of embedded" when you place PS.eps.