And he was correct. A distribution profile, which is what you need to upload to the store, is not linked to any device ID.
I'm sure you'll correct me if I'm wrong, but this page indicates the need for a provisioning profile, which in turn can't be obtained without entering a device ID.
https://developer.apple.com/iphone/manage/distribution/index.action
Now, it appears that Apple doesn't validate the device ID, so I now have two provisioning profiles (development and distribution) that I can hopefully use without owning or borrowing a device.