After a call to remove an object:
bpy.data.objects["Plane"].user_clear()
how do I get a refresh so that the object is no longer in my scene? I still see the object in my scene, although the object property name show a red background in the UI.
Consult the docs.
AFAICT you are under the wrong impression of what user clear does.
Clear the user count of a data-block so its not saved, on reload the data will be removed
This function is for advanced use only, misuse can crash blender since the user count is used to prevent data being removed when it is used.
reload, being when the blend file is saved, and reloaded.