Kirby Tilt 'n' Tumble used samples.

Boxxle for GameBoy is the first game I heard PCM in.

I've finally updated this list some more after a year and a half. You wouldn't believe what I've found!
I took a look at Project S-11, and it does use PCM samples for the music - it sounds at a weird quality, as well - maybe they used a very low sampling rate? I don't know for sure.

pretty much all of the music and sound effects in Vigilante8 are samples. its pretty impressive even tho theres a really obnoxious buzzing over every sound