synergy et al work over IP, so they don't need to be on the same network. however, some of them use bonjour like auto-discovery mechanisms that have to be tunneled between networks.
my view of KVMs is that they're antiquities that predate USB and DVI. you should be able to find a really cheap dumb USB switch (in fact i think i have one lying around that i should probably give away), and a dumb dvi switch shouldn't be that hard to find on monoprice either. i'm not entirely sure if someone builds one box that does both that's an appropriate price (i would say 20$ is the magic number).