Is there some mechanism for preventing a single node storing a single copy of the data, and then spoofing multiple identities and claiming payment as-if the data were stored across multiple nodes?
That's impossible unfortunately - no amount of math can prevent a node from outsourcing the actual storage to a central location that is a single-point-of-failure.
The best you'll ever be able to do is pay enough that there is incentive to do the job right, and/or use social/legal mechanisms to audit what node operators do and then arrange these transactions with specific operators. Not terribly exciting solutions unfortunately...
The obvious solutions are proof-of-work or proof-of-stake, but I can't see how proof-of-work alone would suffice.
Yeah, proof-of-work can only prove IO bandwidth, not where the data is located.
However... interactive latency measurements
can prove data within some sphere of radius t*c. With multiple trusted challenge servers around the world located in co-location centers one could easily prove that the data must be physically present in multiple locations.
You can even do in a fully decentralized way with some extensions to the Bitcoin scripting language by creating a txout that can only be spent by proving you have some data fragment, where the fragment is chosen randomly based on the previous block hash.
Because the fragment is based on the previous block hash, there is a time limit to how quickly the fragment must be retrieved, thereby proving (after sufficient trials) that the data is physically located within a sphere of radius 10minutes * the speed of light - currently this would prove the data may be physically located on Earth, the Moon and Venus, but no other planet. With a second proof-of-work blockchain established on, say, Pluto, we could then easily prove a similar result for data located on or nearby Pluto. (proving the Pluto proof-of-work blockchain is in fact located on Pluto is left as an exercise for the reader)