Why isn't 'Vary: Origin' response set on a CORS miss?
When making a CORS request, if the requested Origin is on the list of allowed origins, the response contains both the Access-Control-Allow-Origin header, and the Vary: Origin header.
The Vary: Origin telling onward CDNs etc that the response was negotiated based on the requestors Origin header value.
The issue is (and I've tested the leading CDN providers), is that if the requestor doesn't provide a Origin header in their request, or an Origin value that is not one of the allowed ones, the response does not include the Vary: Origin in the response.
Should a CDN preforming CORS always respond with Vary: Origin in the response headers? If it doesn't a CDN would believe it can serve the same response to any Origin value. Then again, it would be possible to fill a CDNs cache by making many requests with random origin values.
Answer
Yes. If a request may contain a Access-Control-Allow-Origin with different values, then the CDN should always respond with Vary: Origin, even for responses without an Access-Control-Allow-Origin header. Your analysis is correct: if the header isn't always present, it would be possible to fill the cache with incorrect values.