If there is a record, can he trace back the illegal move and declare
that he wins the game because an illegal move was made earlier?
No. The penalty for a first illegal move is an addition of 2 minutes to the other player's clock. Only a second illegal move loses the game.
According to FIDE Laws of Chess article 7.5.5 -
7.5.5 After the action taken under Article 7.5.1, 7.5.2, 7.5.3 or 7.5.4 for the first completed illegal move by a player, the arbiter shall give two minutes extra time to his opponent; for the second
completed illegal move by the same player the arbiter shall declare
the game lost by this player. However, the game is drawn if the
position is such that the opponent cannot checkmate the player’s king
by any possible series of legal moves
.
Even without a record, can he still win the game because he can
theoretically prove the existence of at least one illegal move made by
his opponent?
No. If no record is being kept of the game then it must normally be blitz or rapid. In that case the illegal move stands and the game continues. According to article A.4.2 of the FIDE Laws of chess -
A.4.2 If the arbiter observes an action taken under Article 7.5.1,
7.5.2, 7.5.3 or 7.5.4, he shall act according to Article 7.5.5, provided the opponent has not made his next move. If the arbiter does
not intervene, the opponent is entitled to claim, provided the
opponent has not made his next move. If the opponent does not claim
and the arbiter does not intervene, the illegal move shall stand and
the game shall continue. Once the opponent has made his next move, an
illegal move cannot be corrected unless this is agreed by the players
without intervention of the arbiter
The illegal move has to be seen immediately (before another move is made or piece touched) and a claim made by player or arbiter.