Multisite installation but do plugins always have to be multisite compatible?

They shouldn’t have to be multisite compatible.

Also remember that, there are two kinds of

  • Passive compatibility: doing nothing multisite specific, just works without breaking anything.
  • Active compatibility: changing or extending multisite specific
    behavior.

In case the plugin you want to use doesn’t say anything about its compatibility on multisites, you just have to try them out, they may break things but they also can work without problem, it depends on what is their purpose.