Docetaxel Alone or in Combination With Vaccine to Treat Breast Cancer

* INCLUSION CRITERIA: * Metastatic Breast Cancer (either male or female) with evidence of metastatic disease (must have radiographic evidence of measurable disease) on computed tomography (CT) scan or X-ray, or evidence of evaluable disease on bone scan that is consistent with metastasis and a life expectancy of at least 4 months. Patients may have received unlimited prior hormonal therapy and chemotherapy. * Histologically confirmed adenocarcinoma of the breast cancer confirmed in the Pathology Clinical Center at National Cancer Institute (NCI), (or National Naval Medical Center (NNMC)) or MD Anderson Pathology Department prior to starting this study. Note: However, if no pathologic specimen is available, patients may enroll with a clinical course consistent with breast cancer and a pathological documentation of the disease. * 18 years of age or greater. * May have received docetaxel in the adjuvant setting at least 12 months prior to study entry. * Able to understand and give informed consent. * Able to avoid close household contact (close household contacts are those who share housing or have close physical contact) for at least two weeks after recombinant vaccinia vaccination 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 3 years of age and under; and immunodeficient or immunosuppressed persons (by disease or therapy), including human immunodeficiency virus (HIV) infection. We have vaccinated over 700 cancer patients and have reported no cases of either self inoculation or person to person transmission of the virus. * Eastern Cooperative Oncology Group (ECOG) performance status of 0 - 1. * Serum creatinine less than 1.5 times upper limits of normal (ULN) OR creatinine clearance on a 24 hour urine collection of greater than or equal to 60 mL/min, standard liver function tests (LFT) limitations for patients receiving docetaxel therapy include bilirubin within ULN and serum glutamic oxaloacetic transaminase (SGOT)/serum glutamic pyruvic transaminase (SGPT) less than 1.5 times the ULN. If transaminases are greater than 1.5 times the ULN up to 2 times the ULN (as currently indicated), then alk phos should be less than 2.5 times the ULN. (Patients with renal abnormalities should be evaluated for creatinine clearance (CrCl) and interstitial abnormalities. A Cr Cl of greater than or equal to 60ml/min measured or calculated and proteinuria less than 1000mg per 24 hours are eligible unless explained by non-renal causes.) * Recovered completely from any grade 3 or 4 reversible hematologic and non hematologic toxicity associated with recent therapy. Typically this is 3-4 weeks for patients who most recently received cytotoxic therapy. Patients previously treated with mitomycin c or carboplatin will require a minimum of 6 weeks. * Hematological eligibility parameters (within 16 days of starting therapy): 1. Granulocyte count greater than or equal to1,500/mm\^3 2. Platelet count greater than or equal to 100,000/mm\^3 3. Hemoglobin (Hgb) greater than or equal to 8 Gm/dL * Must agree to use effective birth control or abstinence during and for a period of 4 months after the last vaccination therapy. * Patients whose tumors are estrogen receptor (ER) positive should have failed primary hormone therapy unless clinically indicated, i.e. in patients with visceral disease or symptomatic bone disease where up front chemotherapy is warranted. Patients who progressed or recurred following Trastuzumab (Herceptin) therapy if a patient is fluorescence in situ hybridization (FISH) positive or immunohistochemistry (IHC) 3+ positive for human epidermal growth factor receptor 2 (Her-2 neu). Those patients who have progressed on trastuzumab may continue to receive the drug by their referring physician. However, if trastuzumab has been discontinued at the time of enrolling on study, it cannot be resumed while a patient remains on study. * Patients randomized to docetaxel alone (arm B) may at time of progression go on to receive vaccine alone if their ECOG performance status remains 0-1, and they do not have any uncontrolled pain or organ dysfunction that would require another intervention such as radiation or chemotherapy. Furthermore, patients initially randomized to arm B that would like to cross over and continue vaccine therapy must meet on-study eligibility and exclusion criteria with the exception of liver transaminase requirement. Patients with liver transaminase levels within Grade 1 by Common Terminology Criteria for Adverse Events (CTCAE) v4.0 (up to 3 x ULN) will be allowed to crossover to vaccine. * Patients should appear clinically stable (in the opinion of the principle investigator) to complete the full 3 month course of vaccination with an anticipated survival of 6 months or longer. * No other active malignancies within the past 12 months (with the exception of non-melanoma skin cancers or carcinoma in situ of the bladder) or life threatening illnesses. * Patients with cardiovascular symptoms should be fully evaluated for signs and symptoms of cardiovascular disease and other standard evaluations including electrocardiogram (EKG), chest X-ray, cardiac enzymes, and echocardiogram as clinically indicated. EXCLUSION CRITERIA: * Patients should have no evidence of being immunocompromised as listed below. 1. Human immunodeficiency virus positivity due to the potential for decreased tolerance and risk for severe side effects 2. Active autoimmune diseases requiring treatment or a history of autoimmune disease that might be stimulated by vaccine treatment. This requirement is due to the potential risks of exacerbating autoimmunity Patients with endocrine disease that is controlled by replacement therapy including thyroid disease and adrenal disease and vitiligo may be enrolled 3. Concurrent use of systemic steroids, except for local (topical, nasal, or inhaled) steroid use * History of allergy or untoward reaction to prior vaccination with vaccinia virus. * Pregnant or breast-feeding women * 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) * 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 * Clinically active brain metastasis, or a history of seizures that have been active within one year * Medical conditions, which, in the opinion of the investigators would jeopardize the patient or the integrity of the data obtained * Prior docetaxel chemotherapy for metastatic disease * Serious hypersensitivity reaction to egg products * Clinically significant cardiomyopathy requiring treatment * Chronic hepatitis infection, including B and C, because of potential immune impairment * Although topical steroids are allowed, steroid eye-drops are contraindicated * Patients who have received prior PANVAC vaccine therapy * Patients with a prior history of allergy to eggs or egg products should not receive the vaccine * Patients with cardiac disease that have fatigue, palpitation, dyspnea or angina with ordinary physical activity (New York Heart Association class 2 or greater) are not eligible. * Prior splenectomy. * Cardiac complications, including recent myocardial infarction or cerebrovascular accident within one year, and/or unstable or uncontrolled angina.