I would still use Maia. It's a wonderful name and it fits a May baby perfectly. MaiaCeleste is my stock combo, but MaiaLucia is just as pretty, if not more so. :-)
LOL. MaiaCeleste was originally on my list, but my husband said it made him think of "celibate". He makes some odd connections, but once he's got one, it sticks. So Celeste is out. Thanks so much! :o)