How can I get "Plane.000" instead of "Plane"? Obviously it doesn't seem to be a problem for too many people, but to me it is simply looking wrong each time I see it.

In my opinion the first object should be called Plane.000 here automatically when every subsequent item is Plane.00x anyway.



And here the next plane should obviously be Plane.002 and not Plane.



Can I somewhere change Blender's behavior here?? (It is really looking very wrong to me...)
I don't recommend doing this, BUT here is a way to change blenders default naming behaviour.  The following needs to be "tightened up" for other names eg will make mistakes with names like "Planet", but will do as a simple example.  

Open a new blender file, run the script below, then add or duplicate planes.  The scene_update_pre handler runs alot.  Any added plane, cube or sphere will be renamed to start at 000.

import bpy
prim_names = ["Plane", "Cube", "Sphere"]

def name_prims(scene):
    for name in prim_names:
        prims = [o for o in bpy.data.objects 
                 if o.name.startswith(name)]
        newprim = scene.objects.get(name)
        if newprim:
            newprim.name = "%s.%03d" % (name, len(prims) - 1)

# make it a handler
bpy.app.handlers.scene_update_pre.append(name_prims)


Remove all scene update pre handlers with: (Note this will remove all handlers, this one and those added by addons, etc)

# remove all handlers
bpy.app.handlers.scene_update_pre.clear()


Otherwise remove it by name

my_handlers = [h for h in bpy.app.handlers.scene_update_pre
               if h.__name__.startswith("name_prims")]

for h in my_handlers:
    bpy.app.handlers.scene_update_pre.remove(h)