In a message dated 8/6/2013 1:23:47 P.M. Eastern Daylight Time, writes:
here is the Berliner Puzzle Plate, January 21, 1901. I'm not sure if this
is the first one, but it shows the use of the name Puzzle since 1901.
According to my notes, this particular Puzzle Plate - the second one
issued by Berliner (#9317/8) - was recorded on Jan 19, 1901. I think there were
three versions, which may account for the slightly later date given here
His first Puzzle Plate (2 piano solos) was #5504, in late 1898
(England). See PHP for more details.