Ha-bayit sheli nimtsa miyamin.
Could one say בימין here? And if so, is there a difference between מימין and בימין?
No, the use of בימין is mostly for political right wing (pronounced bayamin). It can also be used in construct state, like "in the right side of the house" = בימין הבית. Otherwise, the phrase בימין doesn't really exist.
Yamin is the right hand.
So beyamin would be "in the right hand" or "by the right hand". The logic of Hebrew here is the area "from the right hand" or "of the right hand".
This should be a reasonable alternative:
"... nimtzah betzad yammin ..."
Is "my house is to the right" not correct or too imprecise?
Seems ok to me.
How is מ- used instead of על- ؟
Can't I say: הבית שלי נמצא על ימין
הבית שלי על ימין?
No, it doesn't work in Hebrew with על.