The unfortunate answer is that Steam seems to arbitrarily calculate the shortcut ID in a non-repeatable way, as you have found. This change occurred somewhat recently (~1.5-2 yrs ago).

There's an open Github issue describing this problem in detail. There are generally two ways to get the shortcut ID for a non-steam game:

1. Manually create desktop shortcuts from steam's library interface, then inspect the shortcut to retrieve the ID.
2. Run the non-steam game at least once and inspect the contents of screenshots.vdf for recent entries.

Both are not without issues, and hardly able to be automated.