I've been looking into this for a few days and I've come to the conclusion that there is currently no good way to do this.
First, put your pins as a direct subview of the UIScrollView. Now they'll stay the same size, but will move around when you zoom.
In OS version >=3.2 in UIScrollViewDelegate there is -scrollViewDidZoom:, where you can update the pins to the right coords as it scrolls, and this works great. But in 3.1 we're out of luck. I tried having a NSTimer going and updating the coords instead, but it's not performant on the device.
As a fallback what I do is hide the pins when zooming starts (viewForZoomingInScrollView) and when zooming ends (scrollViewDidEndZooming) update their coords and unhide them.