I would think Mr. Mime would get the leaves for Magical Leaf by pantomiming the leaves. If you read his 'dex entry, it says that if he can make the opponent believe something exists, then it will exist. Make them believe he's shooting leaves, and he is.

I don't understand Kirlia getting it, though. Maybe those green horn things can double as leaves? Or maybe (as I reffed it recently in ASB) it just uses psychic power to form objects that look and function as leaves.

As for Diglett... my assumption was maybe it would fire off a sharp bit of earth, causing a scratch/slash/cut. Or, since it is a mole pokemon, it has claws that we just don't see. Aerial Ace... I guess it could just be a fast attack with a bad name (the in-game description doesn't mention anything about flying or anything like that) but I always assumed a non-flying pokemon using Aerial Ace would jump into the air and then dive down.

Cloyster could attract by simply winking and making flirtatious faces, perhaps. I don't think it has to flash the other pokemon to Attract it :p

I think most moves can be explained in one way or another.

But to go the other way (pokemon that don't have moves that should)... why the hell doesn't Ampharos learn Tail Glow? His tail is a freakin' lightbulb, could a pokemon get a more fitting move.