Hata, Jesus Christ, where do you get this shit?
I dunno if Hayate will end up with anyone, but... I can see him going around the various girls trying to seduce them and then realising in about 100 chapters that actually he liked Nagi from the start.
OR
Hayate "confesses" to somebody (Hinagiku or Ruka, if Maria's out of the question), Nagi overhears, gets upset, she somehow has a stone on her (or Hayate gives her one) and the path opens.
Also, am I the only one who thinks Maria isn't who she says? I bet she's actually Nagi's mother, or somehow related to her. Since she has the whole mysterious backstory etc. And she looks kinda like Yukariko, but that could just be Hata drawing characters similarly to begin with.