It does not matter what level you are in. I was level 15 when I beat him. You just need some oran berries. When you are facing moltres and you have low health, eat an oran berry and if your partner has low health toss one to him. It may also be a good idea to carry a reviver seed or two. For recruiting moltres, toss him a red gummi and then beat him. Most of the times it works.
P.S save before facing him.
P.S save before facing him.