I vs Me, special circumstance?

I was recently having a discussion about how annoying it is when people caption their pictures on facebook with "Mary and I." (without completing the sentence no less, with "Mary and I at the beach."

BUT

But with captions, and referencing a photo of someone, which would be correct as a caption?

"Mary and me at the beach." -or-
"Mary and I at the beach." ????

I had someone reply to me saying:
"But if I say, "This is Mary and *I* at the store", I'd be correct, right? The word is functioning as predicate nominative. It sounds awful, but that's the way the existential verb functions.

"Predicate Nominative" and "existential verb" put me in over my head.

Can anyone enlighten me on whether or not it's appropriate to say "Mary and I at the beach" in reference to a photo, or if it should stay as "Mary and Me.." since the 'removing the other person' trick would call for the use of 'me.'

What say ye?