How do we get sidewalks on state maintained streets?

This question was raised by a Strong Towns Member in Maryland:

In Maryland there is a law that prohibits Maryland Department of Transportation (MDOT) from maintaining sidewalks or bike facilities along state roads. The provision is a holdover from the 1990s, when MDOT finally conceded to build sidewalks along state roads. In practice this has been interpreted to mean that MDOT won't maintain anything past the curb. So, MDOT won't design or build pedestrian or bike facilities past the curb without a locality first agreeing to maintain it.

There are several stories circulating where the State offered to build shared-use paths in places like Prince George's County, where those facilities didn't get built because the County/DPW&T never responded to agree to maintain the new paths. It is an uphill battle to change state laws and almost a difficult to get financially strapped communities to agree to long term maintenance obligations.  

What are other ways that we can work to address the need for pedestrian or bike facilities when the state is willing to construct, but when the state highway department is not willing to maintain?