When is a Page Considered Indexed by a Search Engine?

The question of "when is a page really considered indexed by a search engine" came up when I wrote an entry named Google Not Obeying the NoIndex NoFollow Meta Tag. Basically, Google was crawling and listing the page when doing a site: command. The listing did not include page information outside of the URL.

In my mind, Google must have "indexed" a portion of the page, i.e. the URL. How else can Google display the URL when doing a site: command? The URL must be in the Google database (index) for it to show up in any of the search results.

There are those that argue that the definition of being in the index, requires that other information, outside of the URL must be displayed in the URL. I have started a thread that is building up on the topic over at Search Engine Watch named When Does Google Really Index a Page?