Jer, it won't work with paint because paint doesn't have the XOR filter.
Following table shows whats happening B = black, W = white:

Bit 1   Bit 2   XOR   Paint
  B      W       B      B
  B      B       W      B
  W     W      W      W
  W     B       B      B

So you end up with extra black (see line 2) and the overall image will be almost completely black with only a hint of a coded message.  Still, using just paint can indeed give you a clue that you are on the right track by using image manipulation.