Since I messed the puzzle up the first time around and there already is an excellent answer to the previous version, I'm going to share my thoughts on the new version and the previously intended solution for anyone interested. (Please let me know if this is not a good idea for any reason.)
Both puzzles run parallel for the most part until the end. The first major deduction for both is that the white bishop in the top region must be the promoted f-pawn. This can be found out by consideration of the black kings entry route: The pawn structure on the right forbids his entry there, so he must have come from the left. Now, observe that the presence of the white bishop on a2 implies that the pawn on b3 did not originate on a2. (Otherwise, the entry of the bishop would have been permanently blocked.) Therefore, it must be the b-pawn, which moved into place once the bishop had already entered, which means that the a-pawn also must have already moved. Thus, the only possible entryway for the black king was via a3-b2. Since the a-pawn must have already moved when a3 was not under threat, the only option is that it was already on b4, meaning the king came from a4-a3 before. Now, this move is only possible if white had played b2-b3 immediately before. But that implies that the bishop from c1 never had a chance to exit its home square before this sequence. Since it also cannot be present during it (otherwise ka4-a3 was illegal), it must have been captured sometime before. Thus, the bishop in the top must be promoted, in fact the promoted f-pawn.
As a consequence, every other white piece must be real. This makes the entry of the rook(s) and the king into the top region interesting: For the rooke to enter, there must have been an open file - hence, some pair of black (next-to-)flank pawns both captured to reach their final position. This implies that the white king must have entered from the other side, where a next-to-flank pawn had already moved but the flank pawn had not. While we cannot conclude from here, which side did which maneuver, we can conclude that the f-pawn did not promote on the right, since no option for blacks a- and b-pawns allows for its entry after that. Thus, it must have promoted on b8.
We can now tally up the black captures: One capture by the a-pawn, one by the g-pawn and at least 4 by the f-pawn on its way over. This accounts for all the missing black pieces already. Also note that both the a- and g-pawn captures are well in the past and happened even before the black king entered the white premises. Thus, the most recent white capture was by the f-pawn, which is still at least 3 moves back (not even considering any checking issues in the position).
The white captures are more straightforward, the c1-bishop was taken on its home square and the knights were eaten by blacks pawns to let in the rook(s).
Now we are ready to face the final position. The mutual "retro-pin" of the kings can only be resolved by either moving first the queen and then the white king out of the way, or by blocking the line of sight somehow. In particular, until either of these happen, black can only retract pawn moves, and also only two of them, since any more would (for one thing) block in their bishop from exiting well before.
Here, the two positions diverge. I will first lay out the newer version:
At least two white pieces need to (un)move before one of the left black pawns can (un)move. In particular, if it is now whites turn, then black must have just moved a pawn on the right, before which there is no more black move (even an uncaptured white knight cannot reach the diagonal in time). Thus, white moved last. If that move was not Rc8-b8, we have the same issue as before, so that must have been the last move. Before that, black must have moved a pawn on the right. Again, an uncaptured knight would be too slow, so black needs to have one more pawn move available. Thus, the previous white move must have been Bb8-a7, allowing a black pawn to have come from a7. Now, did the black pawn captures happen on the left or the right? If they did on the right, then we are lost - the white knight uncaptured on the last move cannot reach the diagonal in time, so that black can have no more possible move before that. Thus, the knights were captured on the left - which thankfully leaves just a single move time for the just uncaptured knight on b6 to come from d5 and thus allows blacks king to unstep out of this arrangement and solve the tempo issue. This second-to-last pawn move being a capture also fixes the last one: Since the pawns on the right did not capture, the last one of them to move was the h-pawn, so that the full sequence of the last five plies was (in chronological order): Nd5-b6, a7xb6, Bb8-a7, h7-h6, Rc8-b8.
For the original puzzle I had missed that the black pawn captures can have been on the left. The intended solution proceeded with the assumption that they were on the right. The same tempo considerations lead to the only possibilty being a white knight blocking the main diagonal before being captured on g6. The only way that can have happened was therefore ending with the sequence N?-e5, a7-a6, Ne5-g6, h7xg6, Rh8-h7, with the last four plies being uniquely determined.
For both versions, it is then not too difficult to build a proof game from here. In the first you just have to take care to leave enough space for the white king and rooks to shuffle themselves into position before letting the f-pawn in.
