@Tort (Tort) : Please provide an example file, reopen this task when you will do it.

Example

It's not a bug because two scene can have a mesh with the same name, so by default replaceMesh function works only with the object's scene meshes.

The bug is more that BGE doesn't print a message error for this.

@Porteries Tristan (panzergame):
I think that your understanding is wrong.
Even if the scenes are different, the object of the same name cannot exist.
In such a case we cannot identify an object by the name in bpy.data.objects.

The problem seems to come from this commit:

$ git bisect bad
6c9dd174a8bc2cd9a857c96f3ddfdb398aa6f88c is the first bad commit
commit 6c9dd174a8bc2cd9a857c96f3ddfdb398aa6f88c
Author: Mitchell Stokes <mogurijin@gmail.com>
Date: Mon Jun 2 18:52:13 2014 -0700

Fix T39053: Replace mesh actuator does not replace material (only mesh)

The replace mesh actuator was reconverting the mesh data which causes
conflicts with the LoD code. Instead, we just look for an already
converted mesh, which should already be in the scene.

https://developer.blender.org/rB6c9dd174a8bc2cd9a857c96f3ddfdb398aa6f88c

Mesh are shared by library in blender but not in the BGE : the BGE make a copy of a mesh for each scene if at least one object use it. So you can't replace by a mesh not in the object's scene, KX_GameObject.replaceMesh respect this behavior only the replace mesh logic brick respect half it : it does nothing but doesn't print any warning message.

Why not share meshes between scenes ?
It will disallow to free a scene because one of the scene's mesh can be owned in any other object, and the replace mesh brick should always check if its mesh still exist.
Of course we can do like libload : remove all meshes in all objects owned by the freeing library.

@Campbell Barton (campbellbarton), @Mitchell Stokes (moguri), @Sybren A. Stüvel (sybren) : What are your opinion on this report ?

Why not share meshes between scenes ?

Because no room to swing fall.