Damaging Z-Moves don't make accuracy checks.
Similar to moves such as Swift, all damaging Z-Moves skip the accuracy check, meaning they not only have 100% accuracy, but also ignore changes to the user's Accuracy stat and the target's Evasion stat. Furthermore, Z-Moves can even hit a target through Protect and similar moves, though they only deal 1/4 their usual damage in that case.
Status Z-Moves simply add an extra effect to the normal move, rather than creating an entirely new move. It sounds like the extra effect from being a Z-Move applies before the normal effects of the move, so they presumably always work, but the normal effects of the move would still be subject to accuracy if the original move was (e.g. Z-Toxic would always give +1 stage Defense, but might fail to badly poison the target).
How they can fail, is if for instance you moved before the z-move and killed yourself with recoil damage, the z-move will fail.