How do I name a mesh using Python, when I don't know its present name?
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 -&gt; cubes.001

# with some selection, running: separate()
cubes.001 -&gt; 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 -&gt; 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])