So, the bane of my (academic) existence has been finally resolved. Took 15 years, but the paper has now officially been published at Computational Optimization and Applications here, with (read-only) paper available here. You can also download the pre-print here.