If you set the Munchkin code to not track anonymous lead on your site, then only known leads should have a cookie. In this case, you can make the assumption that associateLead was probably called before (or a Mkto form fill out). It will not deal with the situation where cookie is deleted but this will still reduce the associateLead call by a lot.
If you do need to track anonymous leads, then your proposal of writing your own cookie will be the best solution as there is not much info in _mkto_trk cookie to tell you whether this is a known lead or not without doing a lookup.