You might consider hiring an electrical contractor who will cut the drywall and put the coax where needed and then repair the holes. The average satellite tech has no interest in cutting up your walls. You might even find a local retailer who will cut the holes and run the cables, but you will probably have to hire your own drywall guy to repair the holes afterward.
It's never impossible to get a cable to a location in the home, it is only a matter of economics. Some people aren't willing to pay several hundred dollars to have electrical and drywall contractors come out and hide a cable. Other times, its been done in under a few days and the owner never blinked when pricing was brought up.