Based on initial testing:

When you have the recycle bin enabled, deleting modules is done asynchronously.  

The module is marked for deletion in the course_modules table and no longer appears in the list of course modules in course mod info.

Then if you call get_cm() and pass it the "deleted" modules id, get_cm throws an error. See here: https://github.com/moodle/moodle/blob/main/lib/modinfolib.php#L248 

Most of the module deletion functions <mod>_delete_instance() call get_cm() at some point. And the error being thrown in get_cm stops the deletion. Which in turns causes the related adhoc task in MDL-68365 to fail.

However, when the recycle bin is disabled the delete is done synchronously the module to delete is still in modinfo's list of modules so get_cm() succeeds and the deletion does too. It's not the recycle bins fault per say, it's just that most of the module delete behaviours expect get_cm() to work.

The above should be verified to be correct. There may be a few other inputs and steps into the above, but based on initial testing and analysis this should be mostly correct.

There will need to be some more research to figure out the best approach to allow for both synchronous and asynchronous module deletion.