Okaaaay how about she gets her things and starts walking again?

In the middle of the night?

In the rain?

(She hates the damp.)

The next one is farther again. Trudging around in the middle of the night instead of sleeping is not good for her energy level though.

She can deal there is a dead woman she is going to save. One sleepless night never killed anyone, but monsters did.

The rain stops by morning. The genie finds her again by ten. It proceeds to ignore her and keep digging through leaves.

"Will you restore a ghost if I show you a beetle no one's ever seen?" she asks without preamble.

"I will do that if you also show me where you found it and tell me everything you know about it."

"We have a deal. There might be a monster on the way, though."

"If there is I will kill it. Point the way, I will carry you quickly."

She points, and describes the location.

And the genie flies there, carrying her on oddly solid winds. Alarmingly fast. 

Yeah she's too pissed and tired to be alarmed. When they get there, she shows it the live specimen in a jar and the location where she found it. She can tell it everything she's read about what sort of beetle she suspects this is related to.

It doesn't ask questions, just drinks it all in. 

It doesn't seem to be in any hurry to keep its end of the promise.

When she's done she looks at it pointedly.

It studies the beetles before it placidly.

"Are you going to fulfill your end of the bargain?"

"In twenty minutes. I must commit this place to memory so I can return."

"Very well."

And in twenty minutes it asks where the ghost is and whether she would like a lift to that place as well.

She tells it where the ghost is and, well, if it's faster than public transport...

Off they go, then. Flying south at better than highway speeds.

...this is actually pretty cool.

It's still a couple hours to get to the place. Kaede has to explain herself to the government of New York on the way in.

She has helped this genie, she can bring someone back to life with its help, she would like to do that please.

...The genie will get a magical escort, otherwise yes fine.

Sounds reasonable.