I'm currently doing the Diamond Heights scenario, I've progressed quite well, but for some seemingly random reason, guests seem to be getting lost near the entrance to my park. And then 30 seconds or a minute later, they've left the park. I've made park maps sold at £0.10 through out the park, built multiple information kiosks and checked all my paths.

But they're still getting lost! Does anyone have any suggestions as to what I can do to reduce the amount of guests getting lost?

Check your paths some more, they're most likely the problem. Use the guest overview, set to thoughts, summary, click on "I'm lost" which is the step before the exit complaint and then the map button there to see where most of them are. Try to simplify your layout there. Those peeps you described have been searching for the exit so long they lost patience about it, you just never hear from the ones who barely made it home, does't mean your problem has to be near the exit.

http://www.rctmart.com/fossil/PathingSystems.html explains the possible pitfalls very well, it was written for rct2, but applies to 1 just the same. The article about crazy castle has some good stuff about paths as well.
Just never, ever use double wide paths in rct1, even if they just meet in such a way to form a 2x2 I rearrange them, some dimwit will otherwise run in circles there for ten minutes. Using queues as normal paths for the look is almost as bad, did you mayhaps attach the queue at the exit of some ride by mistake?

And of course if such road reconstruction drops peeps on the ground you pick them up and put them back on the path.

If they want to buy a map they'll do it just fine for the default price or a tad more, only reason to sell them so cheap would be if you drain your peeps of their complete cash at the gate, but then you'd have to drop the last 0.10 as well.

Learning to build a path network that your peeps can understand is one of the big challenges of the game, you'll get there over time :-)

Edit: Just remembered something oh so clever I tried in that scenario, entrance to a big coaster on the water near the start of the park, exiting towards the back... confused the heck out of everyone trying to ride it again. Don't do that.

Try making a path from station 2 of the railroad roughly following the tracks along the left side of the lake, connecting back to the existing one where that crosses the water first. So everyone who is up there can go left because it seems shorter to the exit, and now it really leads there.

I'm having a similar problem in the Evergreen Park scenario. The park's base design makes it very difficult to keep guest from getting lost. I have built information kiosks all over the park.

Is there anything else I can do?

Don't let them wander into undeveloped areas, they'll just get bored and grumpy there. Either sell some paths that you wont ever need (Evergreen gardens has plenty of those, free cash) or use the signs found on the benches tab, set to "no entry" to seal off parts of the park for now.

There is no such setting. The game only notifies you of the most desperately lost ones, or however it decides that. Drop the bugger at the exit if you have time, he's wont spend anymore anyway and only drags your park rating down with his whining.

I've seen trainers add useless messages, but never remove them, keep improving your paths to avoid the cause, no way to get rid of the message. Or develop a thick skin about it, if the rating is ok who cares about one guy beeping.

Remember in such disconnected scenarios to always provide a foot path in addition to any other transport means you might have. Once they had enough of your park they won't take the monorail to the exit even if its free and beautiful and the only way to get off that island.

What i've found that really helps on bigger maps is to close off the rest of hte park by using signs with "not entry" written on it. I can't quite remember what map Diamond heights is but that's what I do, narrow it down to a certain area that they can go to and stuff it with rides and stuff, than make it bigger when you run out of room.