The reason you are advised to put a custom post type in a plugin rather than your theme is that in this way the user can keep the cpt even if he decides to switch to another theme. In five years or so, design trends may change significantly and you don’t want to be stuck with a theme, just because it also holds your custom post definition.
Now, if you look at the hook order, you see that mu-plugins are loaded before everything else. This means that the main function of the plugin is registered by the time you initialize your theme at the after_setup_theme hook. At that point you can use function_exists to check if the plugin has been loaded. If not your can notify the user or do something more drastic, like stop loading the theme.
By the way, it is not necessary to make your plugin a must use. The plugins_loaded hook is also executed before after_setup_theme, so any plugin function is known to WP before you start initializing the theme.
Also, it is possible to make the dependency a two way affair. If your plugin initializes (as it should do) at the init hook, the theme has been loaded by that time, so you can check for the existence of the theme’s main function and issue a warning to the user that he is not using the theme that is optimal for this custom post type.