Where does the copyright 'license' exist at? Is it in the medium, the UPC, the box, or perhaps more intangible than that?
Why aren't thefts of media (music/DVDs/games) filed as copyright infringement due to lack of meeting of the minds?
The license itself may be entirely separate from copyright. It can restrict your rights under copyright, or it can grant you more rights (provided that they own it), or it can restrict you from doing things not related to the copyright at all. The license is merely a contract. It's important to know that it's a contract, because there are legal protections and doctrines that apply only to contracts (i.e. the meeting of the minds).
On physical products sometimes it is located on the packaging (i.e. "shrinkwrap" contracts) - last time I opened a Microsoft Office DVD (not that recently) it was still printed on the package. Most software nowadays have their license agreements in the installation procedure, where you click "I Agree". For music/DVDs, sometimes that is less clear (sometimes there is no license at all). If there is no license, you are still bound by copyright law - that is, if you copy it, you're infringing the reproduction right, etc.
"Where does the copyright exist at? Is it in the medium, the UPC, the box, or perhaps more intangible than that?"
Thought I was pretty clear I was not talking about a EULA or similar.
E.g. in the EU, doing a public performance of a work is restricted by copyright, as is renting/lending to the public, though neither involves copying. (Don't ask me why someone thought it was a good idea to make copyright cover renting/lending, but there we are: http://goo.gl/WneMs ).