Novel sorting algorithm
well done providing doc strings
sticking to the Style Guide for Python Code makes Python code easier to grasp, especially for someone who didn't write it
to make the naming more convincing, you should factor out sequential_deterministic_stand_in_for_seeing_the_required_result() and sequential_deterministic_stand_in_for_checking_the_result()
As a bonus, this removed implementation detail from the docstrings of "the oracle functions".
the nested loops in oraclesort() seem to iterate all permutations of elements from input_seq - as indicated in the docstring.
Using itertools.permutations() is easier to read and should test sequences of like length, only.
(Strictly faster than the related bogobogosort for not repeatedly checking the same sequence.)
instead of determining the index of the minimum value and using slices to construct input_lst_without_min, you could use just determine the minimum value, compare it to the start of the candidate sequence and remove it from the sequence to sort recursively:
input_lst_without_min = input_seq[:]
input_lst_without_min.remove(min(input_seq))