Hi Amanda,
The Record Type selection on the SFDC profile only controls what kind of record type that the assigned user can create; it does not restrict visibility of those records. From SFDC's documentation:
Users can view records assigned to any record type. As a result, a page layout is assigned to every record type on a user's profile. A record type assignment on a user’s profile or permission set doesn’t determine whether a user can view a record with that record type. The record type assignment simply specifies that the user can use that record type when creating or editing a record.
As a result the Marketo Sync user can see all the records. SFDC's security model is pretty good and it's very unlikely that Marketo can even ignore it.
There's certainly a way to do what you are looking to do through using a combination of role hierarchies/organization-wide default settings and criteria-based sharing.
Here's one possible approach you can try. Keep in mind that I know nothing about your instance and with changing sharing/access in SFDC may have unforseen impact other processes, functionality. If you have a sandbox, I would suggest testing in that environment.
1. Make sure the lead object is not visibile to the Marketo Sync user by looking at the Sharing Settings; if you have 'Grant Access through Hierarchies' turned on for leads, then it is likley the Marketo Sync user's role is in the hierarchy is high enough to see all lead records and may need to move into a different part of the hierarchy where it cannot see the leads; on the other hand, if you do no have 'Grant Access though Hierarchies' turned on for the lead object; you may need to evaluate those settings (is it public read/write?) to remove access for the Marketo Sync user. Essentially you want to 'hide' all leads from the Marketo Sync user as part of this step.
2. Next step would be to create Sharing Setting rules that would create a sharing exception that allows the Marketo Sync user to see the specific targeted lead records. This would require create Sharing Setting rules using the rule type of 'Based on Criteria' (Note that these rules can only be applied to roles or public groups, so you may need to create a public group for your Marketo Sync user). You can then set up a rule that specifies what record type would be visible to the Marketo Sync user.
I hope this helps. Sorry if this was bit log winded.
-mark