I have no experience in submitting Apps to the App Store, so I might be talking rubbish. But one could simply submit two binaries - or linking to the Mac App Store version, as suggested in another comment.

It`s like a bundle; pay once, run everywhere. Cultured Code`s Things for instance could sell such a bundle with a discount.

Some people do that already for libraries that work on the simulator and device. It's a bit of a pain in the ass to do manually, but it's not something that would take apple long at all to add to the toolchain.