Just tried it with the laptop. Works flawlessly with Win7 x64, as I suspected. I can now scan from my laptop and, via the LAN, save the scanned documents in the correct folder on my Win 8 machine. But that's hardly an optimal solution...

Oh yes, this might be of interest too: I used to have an HP Photosmart C6180 all-in-one as well, also connected to my home network via LAN. The Xerox was actually the replacement of this device, since the HP was an inkjet and I wanted a laser printer. I remember that, when scanning from the Win 8 machine, when both the Xerox and the HP were still installed, I could choose which device I wanted to use for scanning. When I chose the HP, it worked just as it was supposed to. When I chose the Xerox, it failed with the aforementioned error message, and it still does. I now no longer have the HP inkjet, I gave it to my dad because for his use it was a perfect fit.
All this for me is an indication this is probably a simple Xerox driver issue. But I have no idea how to solve it since re-installing the driver does not help.