> cross the border as soon as they get sick

One solution is to put a delay on eligibility. In your example, Maryland would provide free healthcare to anyone who has lived in Maryland as a permanent resident for 5+ years. Much like state universities. There's two different costs and in-state tuition is much cheaper. No more freeloading. Or less, anyway.

Whenever someone tells me, "It's too complicated!" I just think they're lazy. I usually don't say it though, to be polite. Instead I try to walk them through algorithmic thinking in a way that doesn't terrify them that I'll automate their jobs.