If the plan is using the triple match scenario intending to meet the SH requirements, must all of the match be 100% vested?

No, only the Safe Harbor Match must be 100% vested.

Deferrals that exceeds 6% of pay cannot receive a match.
The fixed match and the discretionary match can both be subject to a vesting schedule.
The discretionary match cannot have any allocation conditions if you want to avoid the ACP test.
The discretionary match amount cannot exceed 4% of pay if you want to avoid the ACP test.
The fixed match can have allocation conditions, you'll just have the usual coverage testing to pass.
The rate of match cannot increase as deferrals increase.

This design avoids potential problems with the deemed CODA issue.

I would word it as follows:

If the match is used to satisfy ADP safe harbor, it must be 100% vested (because anything used in the ADP test - safe harbor or otherwise is 100% vested) this match can not be discretionary.

if the match is used to satisfy ACP safe harbor it could be discretionary and subject to a vesting schedule.
it can't be greater than 6% deferred or more than 4% of comp.
e.g. a match of 66.66% up to 6% deferred = 4% of conp (66.66% * 6% = 4%)
(plus you could include match used to satisfy ADP safe harbor (provided the enhanced match was not greater than on amount greater than 6% deferred.)