はい！「they may not do it」を「maybe they don’t do it」にすることはできます！まったく問題ありませんし、基本的な意味も同じです。
例: She may not understand this now, but she will when she gets older.（彼女は今は理解できないかもしれないが、年を取ったときにわかるだろう。）
例: Maybe she doesn't understand this now, but she will when she gets older.（彼女は今は理解できないかもしれないが、年を取ったときにわかるだろう。）
例: I may not have the answer you want, but I can find out.（君が求める答えはわからないけど、調べることはできるよ。）
例: Maybe I don't have the answer you want, but I can find out.（君が求める答えはわからないけど、調べることはできるよ。）