Haven’t you already reached the limits on what human ass-probing can teach you?
Nononono, that is my point Aro; my important question would be “how is it that we are we able to have a conversation with you without violating general relativity” - whether the alien travelled here or whether the information is being transmitted somehow makes almost no difference if the alien is from outside our solar system.
Okay. Say the alien replies “General relativity as you believe is wrong, the universe actually runs according to a (insert Terry Prachett reference here) mechanism.”
Can you then be sure his / its answer is absolutely correct? It could be pulling your leg. A human mind behind the ‘alien’ could still be running the scam.
Okay, I know this depends on the complexity of the answer, but I think the quesrtion I am looking for would have an answer instantly verifable to humans, but also as yet unknown to humans.
(Maybe your question does do this, and I just can’t see it.)
One question that would qualify per the OP is: “We detect that about 1/3 of the universe is made up is made up of a strange dark matter that is invisible to our current instruments. What is dark matter and how can we detect it for ourselves?”
Well assuming that it is a realtime conversation (no delay) and thus no time for research. Also assuming the “alien” has advance knowledge of the question. Couldn’t it just be an extremely obscure question that no one could possibly answer instantaneously, but we could verify after a response.
For example:
Exactly how old am I?(down to the number of minutes)
How many buildings taller than 20 stories exist in North America?
What is the sum of the 100th through 200th decimal place of pi?
I challenge any human to give me an exact, instant answer. Maybe this would work Aro?
My post should read
“Also assuming the “alien” has NO advance knowledge of the question.”
Do you want to have sex?
Come on, I can’t be the only wants to…um…nevermind.
Could you ask for the plans to build better technology than we currently have? A decent quantum computer, handheld laser weapon or something else that I presume we can make using existing manufacturing technology but don’t know how to build. Of course the answer wouldn’t be immediately recognizable as correct but it’s still verifiable. We could as questions related to medical technology. How can we correctly and immediately diagnose Alzheimer’s?
Along the lines of mathematical proofs, one could ask for an elegant proof of the 4 Color Theorem.
You could ask them if they would take Bjork back.
I see several problems with this scenario. Why would you expect the alien to know the answer? If someone asked me to prove Fermat’s last theorem I would be unable to do so. If the alien is allowed to do research, I would just say “show me your research device, explain how it works, etc…” That would probably be proof enough. Secondly, do you mean convince me, or convince the human race? If I ask the alien “please prove/disprove the Riemann hypothesis” and the alien scribbles down a bunch of symbols, I probably wouldn’t be able to understand it even if the alien was using earth’s mathematical notation.
If I ask something like “what is the exact population of Earth at this very second” and the alien comes up with a (reasonable) number, I couldn’t verify that either. If the alien could tell me about something in my past that only I know about, that would add weight to the idea that it is a member of an alien species, but why would I expect an alien to be able to read minds or have another method to reveal past events?
My conclusion: There is no satistfactory way to prove anything by just asking one question. You would need a series of questions with a team of experts on both sides. Working under the assumption that it is just I, Arnold Winkelried, and Alien X, engaged in conversation, the thing that would convince me would be visual proof of some kind, as in showing me the research device mentioned in the first paragraph, or else showing me peculiarities of his/her physical body.
I would give them an IQ test. See how smart they are by our standards.
Weird. The only thing I’d want to know is what their home planet is like.
I mean, c’mon! I’d have just made contact with a creature who lives on a planet (presumably) in a solar system that may be NOTHING AT ALL like ours! Their planet might not have a tilted axis! It might have a figure-eight orbit in a double star system! They might not be the dominant creature on the planet, and are fleeing predation!
Okay. GEEEEEEEK.
Oh yeah, and I’d also like to know what their intentions are toward us. 
I think I’d get some smart science-type people together with some textbooks and whatnot, and let them teach the alien everything that we think we know.
Then ask the alien “So, what did we leave out?”
I think that an alien knowing to the proof to some as-of-yet unproven theorem would be impressive, but that an alien being able to school us about something that we don’t even know about yet would lend alot more credence to his/her alienicity.
CalMeacham:
After a bit of Googling, I found the book you referred to:
http://www.google.com/search?q="Robert+Sheckley"++"Ask+a+Foolish+Question"
That seems to miss the point of the OP. The game is not to think of a question the alien would bound to know the answer to, or be able to answer simply, but to find a question that if answered definitively would prove that it was an alien speaking and not a human faker. Of course if you asked for a Fermat proof and couldn’t get an answer, or couldn’t understand the answer you got, it would prove nothing. But if you could get an understandable answer you have a winner.
To answer the OP: I don’t believe you’re going to improve on Sagan’s own suggestion, Aro (or your own about Goldbach), but of course your game is to find plenty of backups, and so I’m sorry I can’t add to the list.
The stuff about “is there a God”, “what’s your planet like”, “fancy a shag” are all well and good provided you know it’s an alien you’re talking to, but until then you might as well be asking Roger C. Carmel.
Everton is on the right track, I think. But I would suggest there is no one question that any person could ask that would work. None of us knows and understands all human knowledge and would know if the answer is outside of human experience.
I think the only proof would be a physical demonstration of alienness, not words.
Which means I cannot prove my identity to any of you. 
Turn your head and cough please.
How about this: What number am I thinking of?
Aliens can read minds, right?
I’d first ask them to describe all intelligent life in the universe and where we sit in the mix.
Could I get some lube before you put that in there again?