i belive that you can remove and recreate the volume replication without stopping the failover service - worked for me some time ago, but you will have to stop failover on some point anyway, to add the recreated volume to it.
or
stop the service, recreate replication and start again, without waiting for it to finish - although im not sure if it will allow it

the point in stopping the failover service is only so that you can add or remove volume from it.