My problem was indeed the same as in the question I linked, in that the get_permalink() call was happening before the post type was registered. I confirmed this when trying to write a work-around that used get_post_type_object(), which worked fine in functions.php but returned null when moved into my plugin.
By referring to the action reference page in the WordPress documentation (which, although it doesn’t mention it, is sorted by the firing sequence of the actions) I could see that the action I was using to get the permalink, init is fired after the one I was using for registering the post type, plugins_loaded.
By moving the code using get_permalink() to the init action, I was able to fix the problem, and now the correct URLs are being returned, with the post type slug as expected.