I love riddles like this.
Has anyone found any good collections of these? Whenever I try to search for riddles online, I end up with mostly results containing wordplay riddles like "what has a mouth but doesn't eat, ..."
Before publishing I found this while trying to see if there was a already a riddle like it out there (closest I could find was the 1000 barrels of wine riddle mentioned at the beginning): https://puzzles.nigelcoldwell.co.uk/
You can also think of this riddle as a very symmetric version of Wordle, where instead of trying to solve for a permutation of letters you're solving for a permutation of years.
SPOILERS FOLLOW as I will be discussing the answer.
Looking at the table, device 3 obviously tells you if the bottle is from the "high" group (8-15) or the "low" group (0-7). So you line up the bottles and start using device 3 on them, and move them into two groups, 0-7 on the left and 8-15 on the right, as you get the results of each test.
Also, once you've found all eight bottles of one group, you can stop testing because all the remaining bottles will be in the other group. If you're lucky this might happen as soon as test 8, but worst case you must test 15 bottles, then you'll know which group the 16th belongs to without needing to check it.
Worst case: 15 tests done so far.
Now look at what device 2 does. For each group, 0-7 and 8-15, it tells you whether that bottle belongs to the "low" half of the group (0-3 or 8-11) or the "high" half of the group (4-7 or 12-15). Furthermore, in each group of eight, once you've identified four "highs" or four "lows" you can skip testing the rest. Worst case, you have to test 7 bottles of each group before you find four of a kind, and can skip at most 1 bottle per group. 2 skips total, 14 tests.
Worst case: 15+14 = 29 tests done so far.
Now you have four groups, 0-3, 4-7, 8-11, 12-15. You use device 2 which will tell you whether each bottle is in the "high" or "low" pair for each group (0-1 or 2-3, 4-5 or 6-7, and so on). Worst case you have to test three bottles from each group before you are guaranteed to find a pair and be able to skip the fourth bottle. So worst case here is 12 tests.
Worst case: 15+14+12 = 41 tests done so far.
Now you have eight pairs that are 0-1, 2-3, 4-5 and so on. The final device, device 0, will tell you whether the bottle you tested is the "low" or "high" bottle of that pair, so you can arrange each pair in correctly-sorted order after testing one bottle. Guaranteed to need 8 tests, with no possibility of luck of the draw changing that number.
Worst case: 15+14+12+8 = 49 tests done and you've arranged the bottles in order from 0 to 15, so you now know the year of every bottle.