huh. that reminds me. i gotta finish pokemon colosseum.

To put this in the nicest way possible,

Ebay. The website for online auctions and rare items.
goto http://www.ebay.com/
type in "game boy color battery cover"

and be prepared to pay anything from rm15 to 35 depending on how sadistic a seller you happen to meet.

As for alternatives in real physical stores, I can tell you that my hunt for a GBA battery cover in 2005 led me to the Golden Arcade in Sham Sui Po, Hong Kong. The shop was in one of the dark corners of the place, where the gutted innards of consoles past hung lazily from the ceiling. The shopkeeper was an old lady with a toothless grin and this loud grating voice.

paid about RM5.

needless to say its hard to find.