In fact a cookie is not always necessary for Pre-Fill to work, nor is Munchkin. Clicking a tracked Marketo link will Pre-Fill a form even if cookies are completely disabled and Munchkin is not loaded. However, the ongoing session will not be associated with the lead in that case, only the pageview with the form on it.
Merely interacting via email, as in clicking a tracked link, doesn't set a cookie. It's only after the subsequent pageview (visiting the original target URL) that a cookie is set. And if the asset being targeted is a PDF, for example, no cookie will result.