We had this same issue and I never got it work using the exact token structure you provided. Our solution was to create a SFDC Formula text field on the lead ("https://yourinstance.salesforce.com/" & Id) that generates the URL. It's only visible to our custom sync user and works well for our alerts coming out of Marketo.
What do you mean the "sample send" is failing?
To get that token to resolve requires you to send the Sample as if it came off a real lead. This function is best used from the main UI by right clicking on the Alert Email.
The only time i've seen it fail is if SFDC ID isn't properly seen by Marketo, which then means you need to do a hack like Emily suggests.