Hi Matt,
I see one issue in each of the examples you provided. First, the associateLead call, you're setting th Email field to an empty string, so even in the call submits to your marketo instance, it can't associate the anonymous cookie into a known lead record.
EDIT: You're probably setting this dynamically in the server so this is probably a different issue.
Second, with your syncLead call, I don't see a marketoCookie parameter. in the XML, the leadRecord needs a marketoCookie submitted after the leadAttributeList in order to perform a known-anonymous lead association. Unless this is already a part of your LeadRecord class I don't see a way that this would work.