I'd hardly call the Pontic coast "the very heart of the Scythian domains" (mind you, Scythia isn't just modern Ukraine, and even then, the coast is only a thin line along it), nor would I say the Greek colonies there were very co-operative. But most of all, I'd point out that the Black Sea is a pretty treacherous sea, especially during some times of the year.
Though, you may be right - if the Persians had really, really set their mind to it, they might have been more successful in their Scythian campaigns. So could have Alexander. But then they'd have to divert their attention from other, more useful areas.