While I agree that finding spells/skills would be much more of a hassle compared to learning them from a single trainer, the 'basic' skills/spells would be easily found.
Eg, someone exploring Olde Yorke (and its surroundings) would find basic cleric spells, as well as kick.
I'm guessing that new players will probably head off to 'newbie' areas to level, and if the mobs in these 'newbie' areas teach these basic skills/spells, there shouldn't be much of a problem.
But if you've remorted, you should be by then able to explore and find these mobs.
After all, these makes the skills more valuable, and more of a challenge to the player.
I mean, think of it this way. If you play a game, and it's easy to get the best eq, best skills, I think you'll lose interest in it pretty fast. But if you manage to achieve something difficult without a walkthrough / help, you'll get a sense of accomplishment and renew your interest in it =)