Inclusion Criteria:

- Histologically proven adenocarcinoma of the prostate with evidence of metastatic
disease including any of the following:

- Lymph node positive and prostate-specific antigen (PSA) at least 10 ng/mL

- Bone scan positive and PSA at least 10 ng/mL

- Prior radical prostatectomy with rising PSA and PSA at least 2 ng/mL

- Prior radiotherapy and PSA at least 10 ng/mL

- Prior cryosurgery and PSA at least 10 ng/mL

- PSA criteria does not apply to patients who are assigned to group B of this
study and were previously treated on vaccine trial DFCI-96079

- No symptomatic metastatic disease (no bony pain)

- Complete HLA typing required

- Performance status - ECOG 0 or 1

- WBC greater than 2,000/mm^3

- Platelet count greater than 100,000/mm^3

- Bilirubin less than 2.0 mg/dL

- SGPT less than 4 times upper limit of normal

- Creatinine less than 4.0 mg/dL

- No altered immune function such as eczema

- No autoimmune diseases such as the following:

- Autoimmune neutropenia, thrombocytopenia, or hemolytic anemia

- Systemic lupus erythematosus, Sjögren's syndrome, or scleroderma

- Myasthenia gravis

- Goodpasture's syndrome

- Addison's disease, Hashimoto's thyroiditis, or active Graves' disease

- HIV negative

- No allergy or untoward reaction to prior vaccinia (smallpox) vaccination

- No hypersensitivity to eggs

- No prior or concurrent extensive eczema or skin disorders (e.g., extensive psoriasis,
burns, impetigo, or disseminated zoster)

- No other concurrent serious illness

- No active infection requiring antibiotics until infection has cleared and antibiotics
have been stopped for at least 3 days

- Fertile patients must use effective contraception

- No close contact or household contact with the following high-risk individuals for at
least 2 weeks after each vaccination:

- Children under age 5

- Pregnant or nursing women

- Individuals with prior or concurrent extensive eczema or other eczematoid skin
disorders

- Individuals with other acute, chronic, or exfoliative skin conditions (e.g.,
atopic dermatitis, burns, impetigo, varicella zoster, severe acne, or other
open rashes or wounds)

- Immunodeficient or immunosuppressed individuals (by disease or therapy) such as
those with HIV infection

- See Disease Characteristics

- See Endocrine therapy

- Prior vaccinia (smallpox) immunization required

- No other concurrent biologic therapy (e.g., interferon or interleukin) for cancer

- No prior chemotherapy for metastatic disease

- No concurrent anticancer chemotherapy

- No prior hormonal therapy for metastatic disease

- Prior neoadjuvant hormonal therapy followed by prostatectomy or radiotherapy allowed

- Patients previously treated with recombinant vaccinia-PSA vaccine may have hormonal
therapy since discontinuing that treatment (Group B)

- No concurrent hormonal therapy or steroids

- See Disease Characteristics

- See Endocrine therapy

- No concurrent radiotherapy

- See Disease Characteristics

- See Endocrine therapy

- No prior splenectomy

- At least 3 days since prior antibiotics

- No concurrent immunosuppressive treatment (e.g., after organ transplantation)