Home automation: Adding relays in series vs parallel
How does one tackle this problem in home automation systems, without
  the need to rewire my entire house?


Well, you can't avoid a bit of rewiring. The circuit you need is this: -



Either switch (relay or manual switch) can reverse the situation and fully control the light. I might also add that you cannot know whether your relay has activated the light or deactivated it. However, if you sensed current you could determine if the lamp had turned on providing the lamp is working. Call it extra functionality if you want.

An alternative way of wiring it is like this: -



Functionally it behaves as an exclusive-or gate.

If you want to add a relay to an existing installation that already does this you need a 2 pole changeover like this one shown in the middle: -



In fact you can continue to add 2 pole changeover switches to your heart's content to give you the same functionality but controlled from multiple positions.