This study is designed to define optimal doses of Dysport and evaluate its efficacy and safety compared with placebo for the treatment of vulvodynia. The study will consist of a dose escalation stage (Stage 1) and a dose expansion stage (Stage 2). Both Stage 1 and Stage 2 will consist of a double-blind period (with treatment cycle 1; Dysport or placebo) followed by an open label treatment period. One or two optimally safe and effective doses of Dysport selected from Stage 1 will be further investigated in the Stage 2.