That's the funny thing about percentages. 1% chance doesn't mean your going to find one every 100 battles… it means every time that'll be your odds. It mights take 500 battles... or just one.
Same with the damn shinies, only on a much worse scale. Every single encounter there's a 1 in 8000 chance... but that doesn't mean after 8000 fights you'll find one.
Really, I think they could up the shiny % just a tad. If shinies absolutely must stay super rare with the sparkles and all, give something inbetween. Just a plain alt color, thats 1 in 100. Shiny can still be uber rare. Its what Monster Racers (a blatant poke clone) did, and it worked well. Thei shinies were just rare enough to be special, but not so uncommon you never saw one, or couldn't find one if you hunted for a bit. (And they generally had better stats and moves too.)
That game also had randomized move pools, so you could catch 8 of the same thing and they'd all be different, post game wild starters, and amazing color customization... and the heals at the pokecenter places were instant. Didn't have anywhere near the actual gameplay depth of pokemon, (side effect of being a racer instead of turn based combat) but it had a lot of things right for a first time out.
I mean beating an audino nets like 2500 xp with egg on, its insane. most pokemon i fight in wild only give like 400 at best.
Yeah, Audinos are sweet sweet pinatas of exp. Especially later when they're level 50 and only have 1 attack move, 2 moves that do nothing to you, and one move that heals you.
Try taking in a level 1 monster with an experience egg against an Audino. It gets like 14,000 exp and will get to its mid 20's in the first shot.
There's a reason the evolution threshold got pushed up to the 40-60 range for this game. Anything that evolves at 20 can be done in one or two battles now.