Is this position legal?

That's kind of the point; proving something is impossible is more tiresome (and boring) than showing something is possible. Besides, a well-designed retro problem usually has a very unique way to unlock it, which may be equally hard to find as you attempt to prove it's impossible. (See this, where my mistake is at the very last step, so the answer (which is positive, "possible") will require you to tread through my very same steps and then a little more.)

Re your problem: I bet last move was fxe6 e.p. Time to go to solve it...

Aww, bummer. The position is possible; last moves were -1... f5xNe6+ -2. Nd8-e6+. Black promoted a pawn to a knight. Nothing fancy, actually. It would have been great if it could be proven Black didn't make any promotion or something; the proof that en passant was impossible is actually neat, even if on the easy side.

That position is legal.

There is nothing inherently harder about illegal vs. legal positions. Some illegal positions are very easy to prove illegal, such as...

like how this one is also illegal

Yes - more obvious 'bad pawn structures'.

There is also the unretractable check:

Yes, but the vast majority of illegal positions are more complex than spotting some pawn structure like that. 

I'm not so sure. Got any proof?

How about this?

I count 9 white pawn captures required and 15 missing black units, so yes it's legal.

Here are some old puzzles made by cobra91 (he hasn't been active on these forums for years):

1.

2.

3. (white to move)

4.

5. (white to move)

6.

7. Also, here is the actuall first "retro" puzzle I composed (easy). I found out that I was trying to be funny in the original thread, like 5 years ago, so I added the original text if anyone is interested (let the cringe begin...):

"Background:

1) The black army invited the white king to a party - with a promise that there will be no checkmates involved. Surprisingly, the white king did not make it to the after party.

2) You have been assigned by the Federal Union of Chess (FUC) to investigate the crime scene and find out what the hell happened.

Legal or illegal? - that is up to you to decide." (last 4 moves?)

P.S. the original solver of my puzzle requested to join the ranks of the Federal Union of Chess (FUC), but he had been rejected due to his past expressions on this site (he actually said publicly in these forums that he "prefers white" and that he "doesn't like black"... some people) 

It's clear to ME that black took (1)...h2xg1=R+ (2)Nh3xg1. I'm too lazy to go any farther, BUT, I'm sure there was another White piece dancing around that got captured on move -2.

Also, here's "mine" (saw this in a book)

Here are the rules:

(1) No visible piece (excluding pawns) have moved.

(2) There is an unknown on h6. (In other words, there's some piece there that's neither a king or a black pawn.)

(3) The kings were never in check.

(4) White started without his knights.

@shoopi: I've been through that other long thread which was interesting too. The second puzzle though appears to be by T.R. Dawson 1911, as cited by myllyniemi in this thread.

Ah, I see. I just assumed he composed it, but if I recall he did post some unoriginal puzzles without giving credit to the composer (maybe he wanted to avoid people searching for the answer?).

Thanks for letting me know anyway.

e4e5dude (#1433):

Very satisfying.

@shoopi: the last one should be Rg6-g3 - f4xg3. Nh3-f4 - g3xh2. Nf4-h3 - Ng1-f3+. Nh3-g1 - h2xg1#

shouldn't be, I think there are 7 captutable pieces, one bisshop, two rooks, two knigths and a Queen. Furthermore there is the h8 pawn.

A bishop cannot be captured since both could never get out and are useless. The h2 pawn however could be captured. The only trick is that it cannot be captured on h2.

P.S. if anyone feels like solving any of the other puzzles feel free to do so.