I think it's pretty simple. Let's take an object called cubes which is one mesh consisting of several disjoint cubes that you want to separate.
# with some selection, running: separate()
cubes -> cubes.001
# with some selection, running: separate()
cubes.001 -> cubes.002
if you then deleted cubes.001 and ran separate() on cubes.002 blender will automatically find the earliest unused object name
# with some selection, running: separate()
cubes.002 -> cubes.001
I think this is how it works, at least there's a logic to it. (Tested by seeing what happens in the outliner if I do this manually for a few iterations.
The reason this isn't a very convenient process is because you are calling a function which is used by the user interface, and doesn't need to return the names of the new objects.
A simple snippet using Python's Set class to find out which scene objects are new in the scene after such an operation is:
# before
A = set(bpy.data.objects[:])
# after operation
B = set(bpy.data.objects[:])
# whats the difference between sets
new_objects = A ^ B
print([o.name for o in new_objects])