To my knowledge the English (whose powerbase was far closer to Caledonia than the Romans') only succeeded in subjugating the highlands after they constructed several military highways into the mountains. This gave their armies the opportunity to quickly mobilize and suppress any local discontent. The Romans didn't have this option: they could have marched in Caledonia all they liked, but the locals would simply scatter and reassemble when the Romans had left. Lack of agriculture in combination with lack of roads made stationing garrisons not viable: no foraging and difficult resupplying. And due to poor communications they would have need many of these garrisons.

In any case, the Picts were only part of the problems that the Roman garrison on Britain faced. Raiding Irish were also a major problem. The sea certainly didn't seem to impair them.