I think there are probably a couple of issues that are limiting the effectiveness of quickstone_tpl.
Firstly, if the number of objects stored is not much less than the size of the array (which is a power of two that starts at 1024), then when an object is deleted, it's id is likely to be reused fairly soon. This is only likely to be an issue on larger maps (e.g. Bridgewater Brunel, where the highest convoy id is 8191, which looks like it was probably purchased just before convoy 1)
Secondly, I think 'next' is currently reset to 1 whenever a save is loaded. This could easily result in small stop ids being reused in any size of game.
I think the simplest improvements will be to save and load 'next' (which I think can be done at any point in the save/load routine), and to implement your suggestion of cycling through all 65535 possible values instead of looping over a smaller array (this might mean slightly more space is needed in memory, but it's at most 1.5MB total on a 64 bit system, and it shouldn't increase the save size).