The best patcher is, in my opinion, ppf-o-matic because it verifies that the BIN file is correct for the patch. But I'm puzzled. If it was a 50Hz/60Hz thing, you'd get jitter. If it's just NTSC, well that comes out of the PS2 and if your multiregion TV is properly set up, it should play. But remember that NTSC-J is not the same as NTSC-US.

You probably need to convert the signal to AV using the fully loaded SCART lead. Also, borrow a PAL only TV and see what happens.