Awesome! Thanks, Kyle.
The next one starts with a K!
Guesses Remaining: 13
You're correct that some starting letters are much more difficult than others. For instance, while only 14 Pokemon begin with the letter N, a whopping 94 start with S, more than any other letter. However, I did some quick calculations and found that there are two S-Pokemon with letters that match 44 other Pokemon. In other words, if either "Sharpedo" or "Swadloon" return an answer of "S*" then you can immediately rule out the guessed Pokemon and 44 others; any other response will be a clue that would rule out even more Pokemon.
In fact, I've played out one possible chain... if the guesses of Sharpedo, Sceptile, Spinarak, and Samurott don't reveal any letters, then there will be only 4 S-Pokemon remaining, so a maximum of four additional (and intelligent) guesses will solve the puzzle. Since we can speculate that, in virtually any scenario, you're likely to rule out more Pokemon by getting a clue than by not uncovering any information, you should be able to solve any S puzzle within eight or fewer guesses. Now, that's not to say that every guess will always be optimized for maximum efficiency in actual gameplay, but considering that there are more S-Pokemon than Pokemon of any other letter, that's still a pretty fast solution chain when the limit is 13 guesses.
Anyway, I just figured I'd share that with you guys. Use the information however you like. *shrugs*