I'd also suggest you go for the 15 or 17 inch PB for gaming.
But, I have played both Halo and the UT2004 demo on my 12 inch PB (768 MB RAM), and they both run OK (well, I'll qualify this below). I haven't played any multiplayer Halo, but I've played the entire single player game through a couple of times, and it was playable at 800 by 600.
UT 2004 can be run in deathmatch and capture the flag games reasonably well, even at the screen's native resolution. Other game types are sadly unplayable.
Both games are much choppier on the 12 inch iBook, although my girlfriend does manages to play UT 2004 with me. 200 Mhz, a higher RAM capacity, and a larger cache do make a difference, but truth be told, neither are gaming machines.