I'm not anywhere near being well-versed in astronomy, so I cannot judge how hard that problem actually is, but let me present a counterpoint/food for thought:

40 years ago, we launched a probe with what we though as of then as being a nice, permanent map of our location. Since then, we learned that there are many more 'beacons' in the universe than those we have chosen and pointed out in our 'map', and they change randomly or pseudorandomly, so with our current knowledge, receiving such probe with such map, we would be SOL to decode it.

But, 40 years ago, there was a term 'supercomputer' which meant an 80 MHz, 5 ton, >100 kW-eating monster. Nowadays, we carry billions of 150 gram glass slates in our pockets with 100-times the computing power, use it to play games, and we throw around desktop/rig computing power to shift balances between virtual bank accounts (PoW-based cryptocurrencies). What would be an unthinkable feat on the planet-wide energetic and hardware level back than, a grad student can do on their gaming device (CUDA etc.) nowadays as a semestral project, building on existing open-source libraries and published reproducible research.

What will be possible [on our humanity scale] in another 40 years? 400 years? 40000 years?

Wouldn't they just intercept the probe and immediately think, oh, species 5618 thought back then that a dozen of pulsars engraved on a metal disk would make a good map, how cute, let's run a configuration-search on our astronomical recordings and on next orbital period, a PhD student presents an interstellar-conference paper on three possible locations in the known history where and when the species 5618 would observe just this specific pulsar configuration recorded on the probe...
Ok, what if they started recording the observable universe only after we recorded our map? They may not have the exact stellar configuration in their big data clouds, but using SETI-like-network, in another orbital period, they will simulate historical pulsar configurations back before they started recording them and extrapolate similar results.
This is just a 'linear' prediction on our technology, but what about a complete paradigm shift? What if they can browse in a block universe just like we page through a book and can just rewind and fast forward looking in the spacetime searching for the configuration recorded on the probe?

Or, we will develop FTL in tens/hundreds/thousands of years, overtake the Voyager with spacecraft just like taking off a private Cessna at a local hobby airport, grab it as a historical artifact for the museum and launch a better map, or, we would know better by then and rather quietly destroy it, remain silent and be thankful it wasn't seen by anything (Hawking's position on contacting alien life).

An earth bound semi-fictional example:
Say a secluded culture thinks that recording rains, droughts, good and bad harvests will benefit their children. Some time later they will find that they have a full Library of Alexandria of records and noone, never ever, in many human lives would sift through all the recordings to find anything useful. Some more time later they will even find about climate zones and think that their collected records are truly worthless and useless.
On the other hand, if our current selves find such records - if they are fairly recent, we have complete satellite imagery of the place. We have pretty nice worldwide temperature, rain, air pressure recordings. If it is a bit older, we still have more sparse weather records, so with some effort, we can still search for their rain-drought patterns. We can carbon date it. We can or cannot see our atmospheric nuclear tests in their smelting. We can digitally cross-reference digitized historical written records from many cultures (probably not now, mind you, semi-fictional). We can manually cross-reference their observations with known folklore from around the world. We can drill Antarctica/permafrost layers to evaluate climate back then. We can date it before/after/around great extinction events, geological eras at least...

Just because we just realized that the IRL situation is much more complex than we thought, it doesn't mean that what we recorded back then and sent out is "hopelessly wrong" [and useless].