It seems that a new site is going to have to wait it out. I think that the best plan is to target MSN first. Wait about 2 months and check out your postions in MSN and Yahoo. I think at the moment, Yahoo is really messed up so I wouldn't ever target Yahoo unless I have a seperate site for just targeting Yahoo. So target the smaller SEs while you wait out the sandbox.