Inclusion Criteria:

- Histologically confirmed carcinoembryonic antigen (CEA)-expressing carcinoma

- Metastatic or locally advanced disease

- Tumor accessible for biopsy

- Must have received ≥ 1 prior systemic regimen for metastatic disease

- No known brain metastases

- Performance status - ECOG 0-2

- Performance status - Karnofsky 60-100%

- More than 6 months

- Absolute neutrophil count ≥ 1,500/mm^3

- Platelet count ≥ 100,000/mm^3

- Bilirubin ≤ 2.0 times upper limit of normal (ULN)

- AST and ALT ≤ 4.0 times ULN

- Hepatitis B negative

- Hepatitis C negative

- Creatinine ≤ 1.96 mg/dL

- Creatinine clearance > 50 mL/min

- No persistent proteinuria

- Protein < 1,000 mg by 24-hour urine collection

- No urinary sediment abnormalities

- No symptomatic congestive heart failure

- No unstable angina pectoris

- No cardiac arrhythmia

- No clinically significant cardiomyopathy requiring treatment

- No impaired function (i.e., ejection fraction < 50%) for patients who have not had
prior vaccine and are asymptomatic

- HIV negative

- No ongoing or active infection

- No history of allergic reaction to eggs or egg products

- No history of allergy or untoward reaction to prior vaccinia vaccination (e.g.,
smallpox immunization) or to any of its components

- No history of or active eczema or other eczematoid skin disorders

- No atopic dermatitis

- No other acute, chronic, or exfoliative skin conditions, including any of the
following:

- Burns

- Impetigo

- Varicella zoster

- Severe acne

- Other open wounds or rashes

- No immunocompromised condition

- Not pregnant or nursing

- Negative pregnancy test

- Fertile patients must use effective contraception during and for ≥ 3 months after
completion of study treatment

- No sexual contact for 3 weeks after each vaccination treatment

- Must be willing to undergo tumor biopsy

- No psychiatric illness or social situation that would preclude study compliance

- No life-threatening illness

- No other active malignancy within the past 2 years except nonmelanoma skin cancer or
superficial bladder or cervical lesions treated with surgical resection

- No other uncontrolled illness

- Must be able to avoid close household contact with the following individuals for ≥ 3
weeks after vaccinia vaccination:

- Pregnant or nursing women

- Children under 5 years of age

- Individuals who are immunodeficient or immunosuppressed by disease or therapy
(including HIV infection)

- Individuals with the following conditions:

- History of or active eczema or other eczematoid skin disorders

- Atopic dermatitis

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

- No concurrent influenza vaccine

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

- No concurrent steroid therapy, except topical or inhaled steroids

- No concurrent steroid eye drops

- More than 4 weeks since prior radiotherapy and recovered

- More than 4 weeks since prior surgery and recovered

- No prior splenectomy

- No other concurrent investigational agents