What you're describing might be simple if the volume up/down buttons directly operated counter circuitry, but it's unlikely that they do so. More likely, the buttons are sensed by software within the phone that attempts to make the user interface work in a manner which would be helpful for a human operating the buttons (e.g. the longer a button is held, the faster it repeats) but would make it harder to control electronically.
I'd suggest that the most reliable approach is to probably use a microcontroller to send various lengths of up/down pulses to the phone at various rates until you figure out the fastest rate at which pulses can be sent while getting predictable behavior. Then have the microcontroller keep count of how many times the rotary encoder has moved left or right, as well as how many up and down pulses it has sent, and send out pulses whenever the numbers don't match up.
This will be harder than using a simple circuit, but it will mean that turning the knob four clicks to the right quickly will have the same net effect as turning it four clocks slowly. Other approaches are likely to, at best, yield behavior equivalent to holding the up button while you're turning the knob clockwise (but ignoring the speed) or holding the down button while you're turning it clockwise (again ignoring the speed). Not nearly as helpful.