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.
This should be a reasonable alternative:
"... nimtzah betzad yammin ..."
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".
Is "my house is to the right" not correct or too imprecise?
Seems ok to me.
How is מ- used instead of על- ؟
I agree with TRH_blue.
Can't I say: הבית שלי נמצא על ימין
הבית שלי על ימין?
No, it doesn't work in Hebrew with על.