[Butz]

They shouldn't follow you all the time because like Tyhm said :

it's a little TOO Zelda to have a fairy following you around...

But how about if there's a place where you can hire them out as helpers by like paying by the day in gralats.(Graal Day mind you) then they can fly with you and use their magic to protect you from others who try to attack or PK you, (Or maybe you can give them battle commands like attack *playername* or defend me or they can cast a spell and whisk you away to safety..) There could even be a quest where you need to have one with you so it can fly in a little hole and push a button to open a door or something.
Just ideas really.