Major Section 11.4.4 in protocol mentions that upserts are not supported against media entities and, more importantly, that services MUST fail an update request to a URL that would identify such an entity if it does not exist.
Given the fact that the service can't be using service-generated keys for these entities and the client apparently already knows how to compose/identify the individual media entities in such collection, why not allow upserts as well?
PS Also noted that in v4.01 we've added "single-valued non-containment navigation properties" to the exclusions list as well. Couldn't quickly recall/figure out the issue but shouldn't that only be if there is no navigation property binding?