Inclusion Criteria:

- Histologically confirmed stage IV melanoma

- Multiple primary melanomas allowed

- Metastasis may be from a cutaneous, mucosal, ocular, or unknown primary site

- Measurable disease by Response Evaluation Criteria In Solid Tumors (RECIST criteria)

- Must have 2 extremities uninvolved with tumor

- Must have at least 2 intact (undissected) axillary and/or inguinal lymph node basins

- Prior sentinel node biopsy may not have violated the integrity of a nodal basin

- This extremity may still be considered for vaccination

- Human Lymphocyte Antigen (HLA)-A1, -A2, or -A3 positive

- Prior brain metastases allowed provided all of the following are true:

- Surgically resected or treated with gamma-knife or stereotactic radiosurgery

- No disease progression in the brain for the past 3 months

- More than 30 days since prior steroids for the management of brain metastases

- Age: 18 and over

- Eastern Cooperative Oncology Group (ECOG) performance status of 0-1

- Adequate organ function measured within 4 weeks before randomization:

- White blood cell (WBC) at least 4,000/mm^3

- Platelet count at least 100,000/mm^3

- Lymphocyte count at least 700/mm^3

- Serum glutamic oxaloacetic transaminase (SGOT) and serum glutamic pyruvic
transaminase (SGPT) no greater than 2 times upper limit of normal (ULN)

- Bilirubin no greater than 2 times ULN

- Alkaline phosphatase no greater than 2 times ULN

- Lactic dehydrogenase no greater than 2 times ULN

- Creatinine no greater than 1.8 mg/dL

- Negative pregnancy test

- Fertile patients must use effective contraception

- No other malignancy within the past 5 years except nonmetastatic squamous cell or
basal cell skin cancer, ductal or lobular carcinoma in situ of the breast, or
carcinoma in situ of the cervix

- At least 4 weeks since prior sargramostim (GM-CSF), interferon alfa-2b, or
interleukin-2

- More than 4 weeks since prior chemotherapy (6 weeks for nitrosoureas or mitomycin)

- More than 30 days since prior systemic corticosteroids, including any of the
following:

- Therapeutic doses of oral steroids (e.g., prednisone or dexamethasone)

- Steroid inhalers (e.g., Advair)

- Topical steroids and nasal steroids with low systemic absorption (e.g.,
fluticasone) or steroids with low systemic absorption (e.g., triamcinolone
hexacetonide) injected into a joint space allowed

- At least 4 weeks since prior local control or palliative radiotherapy and recovered

- Recovered from prior major surgery

Exclusion criteria:

- More than 3 brain metastases

- Metastatic lesions greater than 2 cm

- Concurrent radiotherapy

- Prior radiotherapy to measurable disease

- Concurrent surgery

- Concurrent corticosteroids

- Concurrent topical or systemic steroids

- Concurrent chemotherapy

- Prior vaccination with any of the study peptides

- Recent (within the past year) or concurrent addiction to alcohol or illicit drugs

- Pregnant or nursing

- Known or suspected major allergy to any components of the study vaccine

- Significant detectable infection

- Immunosuppression conditions

- Prior or active autoimmune disorder requiring cytotoxic or mmunosuppressive therapy,
except for any of the following:

- Presence of laboratory evidence of autoimmune disease (e.g., positive
antinuclear antibody (ANA) titer) without symptoms

- Clinical evidence of vitiligo or other forms of depigmenting illness

- Mild arthritis requiring nonsteroidal anti-inflammatory medication

- Autoimmune disorder with visceral involvement