zxing on qr codes has always worked pretty well for me, even on fixed-focus cameras like my old 3 that I use for testing. I checked qrafter and it's the same: scanning the code on Kerem's itunes web page is essentially instantaneous on both my 4 and my old 3. zxing won't work on pre-iOS4 iOS releases, but it seems to work pretty well for qr codes even on fixed-focus/non-video iPhone 3s.
This all caveated by conditions, of course. In different lighting conditions and with source types, i.e., emitting, e.g., screens, vs reflecting, e.g., paper, I don't know. I've never had any problem, but I haven't tried to do a comprehensive environmental test.
One small comment, Kerem: I wouldn't use a reverse video (black-white swap) image for the icon.
Partly because it looks wrong. Partly because people might try to scan it.