Here is a solution, which I found immediately after I realized that the puzzle was asking 5. Qe4+ and not 5. Qxe4+. The 5. Qxe4+ version seems much tighter, and I'm not certain that there is a solution.
Note that in this solution, move 12 by Black could be pretty much anything, it doesn't matter.
Explanations will follow but you can already see that
the cryptic clue about Black castling queenside refers to the checkmate position where Black's King and Rook are in queenside castling position, albeit on the wrong side of the board - which is unavoidable due to the 15. ... Kxc1 move.
TRAJECTORY OF THE BLACK KING
The key move to first focus on is
15. ... Kxc1 which implies that out of the eleven first ?
by Black, at least 6 are King moves (more than that if the King makes horizontal or backward moves).
The move
15. a3 indicates that the a pawn hasn't moved till then, which implies that the Ra1 is still on a1, and the Nb1 is still in place as well to allow 15. Kxc1 without self-checking. Any other possibility like Black capturing the Rook at a1, etc. would take too much time and serve no purpose.
Now
There is only one way the Black King can approach c1 with the pawn a2 and Nb1 at their starting position: we need moves ... Kd3 and ... Kc2.
Regarding the first 4 moves: when the first check occurs, the Black King has to be
at c6. Because if it is on column e, or on file 5, it would then need to make backward or horizontal moves, which would be a waste of time, UNLESS it is at e7 and we have a sequence Qe4+, Kd6, Qe6+, Kc5. But then the funny thing is that you could replace Qe6+ with a lot of checking squares, none of them would allow the King to later capture the Bishop and then proceed to d4.
You would waste an extra Queen move to allow that. You could also have the Queen captured by the King, but then you would need to find another piece to come and get captured at d6 later.
A consequence of this is that
the Black d pawn has to move. It moves to d6 to serve the purpose of being captured later (10. Nxd6 is required).
TRAJECTORY OF THE WHITE KNIGHT
It takes Nb1 three moves to get to d6, and Ng1 four. But the Knight on g1 has one of these moves imposed, so this is 3 moves for both.
But remember that the Nb1 serves a puprpose already by not moving: it allows Kxc1 by Black. Therefore moves 7 through 12 by White are made by the same piece, the Knight initially at g1.
FIRST WHITE QUEEN MOVE
After its first move, the Queen must be able to reach e4 with its next move, but a4, f3 or g4 would prevent the Black King to proceed to c6, which allows only one of the four possible squares.
THE WHITE QUEEN AND BISHOP
To get ... Kd3, the e2 pawn must be gone, and therefore so does the Bf1. Also, the Bishop can't stay on its main diagonal and the Queen can't stay at e4 in order to allow ... Kd3.
The most efficient way to get rid of the Bishop is to have it captured by the King at some point. As for the Queen, moving it from e4 is going to serve two purposes: she delivers the required check at move 6. allowing the King to move past it, and she is the piece being taken at d6 later on.
BLACK'S ROOK
a5 is clearly the optimal way to get the rook out in terms of number of moves, and the subsequent rook moves are pretty obvious.
WHICH WHITE PIECES GET CAPTURED ON THE D FILE
The d pawn and the Queen (if ideally placed) can both get there in one move, which is unbeatable.
AFTER MOVE 15
The situation where Black delivers checkmate and simultaneously escapes check can occur only in case of a discovery by the Black King, or if the mating Black piece captures the checking White piece. In the position after move 15, the former is impossible, while the latter can occur, the rook being the ideal mating candidate. For this you need a checking White piece at d1 where the rook can come down. This is how you see that the White Bishop is needed to bring the White Rook to d1.
?
without a+
means that there can't be a+
? $\endgroup$