This sort of error is almost always due to a timing problem. In particular, the fact that you can run a selection which finds the image correctly immediately after the error, tells us that the image does match. So the problem is simply that Eggplant is looking for the image before the software-under-test (Illustrator, in your case) has finished doing the processing that will result in that image being visible on the screen.
Opening and closing a document, in your case, must affect the timing in some way such that the image appears on screen before Eggplant gives up on looking for it.
There are a number of ways to deal with timing issues (see the article “Failure to Find an Image that is On the Screen” in the Using Eggplant manual), but the most common is to use either the WaitFor command or the ImageFound() function, both of which allow you to specify how long Eggplant should keep looking for an image before announcing that it was unable to find the image.