NavList:

You asked, "which other stars" have significant changes in relative positions over decades? 

Among the classic navigation stars, the fast-movers are Rigil Kentaurus (alpha Centauri), Arcturus, Sirius, Procyon, Altair, and Menkent. All of these have proper motions greater than 0.6 seconds of arc annually. In a decade that amounts to a tenth of a minute of arc, the minimum that we would worry about. If you exclude those stars, you could use a decade-old almanac or data source to calculate star-to-star distances with no problem. Note that the actual coordinates of the stars change more quickly than this, so you can't use, for example, the SHA and Dec of Vega from five years ago with a position of Rasalhague from this year. They both have to be synchronized. But if you're planning to observe the angle from Vega to Rasalhague tonight, you could use almanac data from late May of 2014 instead of this year's data. The angle between them hasn't changed in five years. And just to reiterate, any of these systems/tools that provide fixed distances in permanent tables, even if they are recently published, are usually ignoring annual stellar aberration which can amount to +/- 0.3' in an annual cycle for some pairs with distances near 90°. 

Of those fast-moving stars, Rigil Kentaurus has a proper motion of about 0.08' annually and Arcturus has a proper motion of 0.05'. In just two years, careful sextant observations can detect the change in relative angles between those stars and others (that are aligned with the direction of the motion across the sky).

The winner in the proper motion race is a faint star in Ophiuchus called Barnard's Star. It's not visible in sextant scopes, but with a good backyard telescope, its motion is visually apparent within a year or two. Some backyard astronomers check up on it every year and have followed its changing position for decades. Though I have seen it myself a number of times over the past 40 years, I don't really recall the change. I know I have seen it move more than a tenth of degree across the sky relative to the other stars in the same field of view in that time...

Frank Reed