Inclusion Criteria:

- Patients must have a histologically confirmed diagnosis of malignancy, with evidence
of metastatic disease (evaluable disease is adequate), who have not responded to
standard therapy, who have relapsed, or for whom such therapy is not available

- Patients must have a tumor that has been shown to express CEA by immunohistochemical
techniques or have had an elevated serum CEA > 10 at any point during their disease
course

- Patients must have an anticipated survival of at least 6 months

- Patients must be fully informed about their illness and the investigational nature of
the study protocol (including foreseeable risks and possible side effects), and must
sign an informed consent

- Patients must be ambulatory, with an ECOG performance status of 0 or 1, and must be
maintaining a reasonable state of nutrition, consistent with weight maintenance

- WBC >= 3,000/mm^3

- ANC >= 1500/mm^3

- Platelet count >= 100,000/mm^3

- Bilirubin =< 2 x upper limit of normal

- SGOT and SGPT =< 4 x upper limit of normal

- All patients should have an initial urine analysis; the initial urine analysis for
eligibility is: proteinuria grade 0, hematuria grade 0, and no abnormal sediment; any
positive protein including trace values should be evaluated by a 24-hour urine; any
other abnormality in the sediment or the presence of hematuria should be evaluated by
a nephrologist for evidence of underlying renal pathology; patients may be eligible
if the underlying cause of the abnormality is determined to be non-renal

- Normal creatinine is defined by creatinine =< 1.5 mg/dL OR creatinine clearance >= 60
ml/min

- At least 6 patients must be HLA-A2 positive for each of cohorts 3, 6, and 7; once the
HLA-A2 positive quota of 6 has been met, enrollment to that cohort may close at the
discretion of the principal investigator; there are no HLA phenotype restrictions for
cohorts 1,2,4, and 5, although phenotyping will be performed on all patients

- Vaccinia-naïve patients may be enrolled to any cohort

- There must be no history of allergy or untoward reaction to prior vaccination
with vaccinia virus, for patients on cohorts 4, 5, 6, or 7

- Patients for all cohorts should have no evidence of immunocompromise or autoimmunity
as defined by:

- HIV negative by serologic testing; this requirement is due to the potential for
an unacceptable high risk of systemic viremia, if live virus vaccine were to be
administered to an immunocompromised individual; while similar constructs have
been given to HIV positive patients, concern is high for toxicity, particularly
with vaccinia

- No other diagnosis (past or present) of:

- Altered immune function, including immunodeficiency or history of
immunodeficiency; eczema; history of eczema, or other eczematoid skin
disorders; or those with acute, chronic or exfoliative skin conditions
(e.g. atopic dermatitis, burns, impetigo, varicella zoster, severe acne, or
other open rashes or wounds; this requirement is due to a potential
unacceptable high risk of systemic viremia, if study vaccine were to be
administered to an immunocompromised individual

- Any autoimmune disease such as, Addison's disease, Hashimoto's thyroiditis,
or systemic lupus erythematous, Sjogren syndrome, scleroderma, myasthenia
gravis, Goodpasture syndrome active Grave's disease; this requirement is
due to the potential risks of autoimmunity

- No prior radiation to > 50% of all nodal groups

- No concurrent use of systemic steroids, except for physiologic doses for
systemic steroid replacement or local (topical, nasal, or inhaled) steroid use

- Patients must have recovered from the reversible side effects of prior therapy

- Patients must be willing and able to travel to Georgetown University Hospital for
treatment and follow-up during therapy and at least monthly thereafter until there is
evidence of disease progression

- Patients must be able to avoid close household contact (close household contacts are
those who share housing or have close physical contact) with persons with active or a
history of eczema or other eczematoid skin disorders; those with other acute, chronic
or exfoliative skin conditions (e.g., atopic dermatitis, burns, impetigo, varicella
zoster, severe acne, or other open rashes or wounds) until condition resolves;
pregnant or nursing women; children under 5 years of age; and immunodeficient or
immunosuppressed persons (by disease or therapy), including HIV infection

Exclusion Criteria:

- Recent major surgery (within 21 days)

- Frequent vomiting or severe anorexia

- Pregnant or lactating women; this requirement is due to an unacceptable high risk of
CEA antibody transfer, which may be potentially harmful to the developing fetus or
infant; (NOTE: women and men enrolled in the study are to practice an effective
method of birth control for at least six months after their last treatment on
protocol)

- Serious intercurrent medical illness which would interfere with the ability of the
patient to carry out the treatment program, including, but not limited to,
inflammatory bowel disease, Crohn's disease, ulcerative colitis, or active
diverticulitis

- The following therapies are prohibited and may not be administered to patients being
treated on this protocol: chemotherapy, hormonal therapy, biologic therapy, and
immunotherapy

- Patients must have recovered completely from any reversible toxicity associated with
their most recent therapy; typically this is 3-4 weeks for patients who most recently
received cytotoxic therapy except for the nitrosoureas and mitomycin C for which 6
weeks is needed for recovery

- Patients with clinically active brain metastasis, uncontrolled seizure disorders,
encephalitis, or multiple sclerosis

- Patients can not have any history (past or present) of allergy to eggs or egg
products

- Patients with history of receiving CEA-containing vaccines are excluded from
enrollment into any of the 8 actual study cohorts; however, patients with metastatic
disease who have progressed (as defined by objective response criteria for solid
measurable tumor; tumor marker elevation alone is not sufficient) on a CEA-containing
vaccine, may be enrolled to this study as they arise if they meet the patient
eligibility criteria, but will be added-in outside of the eight established cohorts,
at the currently established safe dose level; additionally, these patients will
receive only the rF-CEA(6D)-TRICOM vaccine (possibly along with GM-CSF if cohort 7 is
the currently established safe dose level), but otherwise will be treated according
to the protocol as any other patient on study; such additional patients will not
count toward study accrual, determination of primary immunologic endpoints, or the
determination of the MTD