This is something that I really wanted as well, after coming from BF2 to TF2, but after a long time wishing I could have it, we started using
sourcemod map management system, and it is much better. Now every map is chosen as either a vote or a random selection. No more forcing a new map to come up only to have the same map repeat because it was next in the rotation.
I highly recommend it.
Now to address your particular situation, if the newest nextmap plugin doesn't already do this, I bet you could request it as an enhancement.