The Case of Nate Bihldorff
In reviewing Mario Power Tennis, I've noticed Koopa Troopa and Shy Guy to both have "voices" that pre-date Bihldorff's employment.
Given how Shy Guy sounds, do note how similar it sounds to Birdo starting with Toadstool Tour (https://www.youtube.com/watch?v=UWxNh4gMBAo). Now listen to Totakeke, a character clearly based off of Kazumi Totaka (https://www.youtube.com/watch?v=kmv_HwTStH0). Hear the connection yet?
So that's how it is: Koopa Troopa uses sound effects like your typical Goomba and pre-Totaka Yoshi, and Shy Guys and Fly Guys are Totaka.
Nate Bihldorff is a voice of a minion, sure enough; just not those two.
One game he's credited in, Mario Hoops, is one where after a fair amount of research, I believe he voiced the Ninja. Use that as your guide. I'm off.