The goal of this clinical research study is to find the highest tolerable doses of the combinations of lenalidomide and other drugs that can be given to patients with advanced cancer. The safety of the drug combinations will also be studied.

The Study Drugs:

Lenalidomide is designed to change the body's immune system. It may also interfere with the development of tiny blood vessels that help support tumor growth. This may decrease or prevent the growth of cancer cells.

Bevacizumab is designed to block the growth of blood vessels that supply the nutrients needed for tumor growth. This may prevent or slow down the growth of cancer cells. Bevacizumab is no longer FDA approved to treat breast cancer.

Sorafenib is designed to block the function of important proteins in cancer cells. These proteins, when active, are in part responsible for the abnormal growth and behavior of cancer cells.

Temsirolimus is designed to block the growth of cancer cells, which may cause cancer cells to die.

FOLFOX (5-fluorouracil, leucovorin, and oxaliplatin) is a drug combination designed to kill rapidly dividing cells by stopping DNA (the genetic material of cells) from duplicating. Because of a pharmacy shortage of IV leucovorin, patients will continue treatment without leucovorin until it becomes available.

Study Groups (Arms):

If you are found to be eligible to take part in this study, you will be assigned to 1 of 4 study arms. Each study arm will receive lenalidomide in combination with 1 of the 4 drugs/drug combinations described in the "Study Drugs" section above. The arm you are assigned to will depend on what arms are still open and what your doctor thinks is appropriate for you. Your doctor will consider the type of disease you have, other drugs you have received for the disease, and any side effects you may have seen with other drugs when deciding which arm you should be assigned to:

• If you are in Arm 1, you will receive lenalidomide and bevacizumab.
• If you are in Arm 2, you will receive lenalidomide and sorafenib.
• If you are in Arm 3, you will receive lenalidomide and temsirolimus.
• If you are in Arm 4, you will receive lenalidomide and FOLFOX.

Up to 4 dose levels of the drug combination will be tested for each arm. Up to 6 participants will be enrolled at each dose level in each arm. For each arm, the first group of participants will receive the lowest dose level. Each new group will receive a higher dose than the group before it, if no intolerable side effects were seen. This will continue until the highest tolerable dose for the drug combination is found for each arm. After the highest tolerable dose of the drug combination is found, an additional 20 patients will be able to receive this combination dose in each arm.

Study Drug Administration:

If you are in Arm 1, 2, or 3, each study "cycle" will be 28 days. If you are in Arm 4, each study cycle will be 21 days.

If you are in Arms 1, 2, or 3, you will take lenalidomide by mouth 1 time each day during Days 1-21 of each study cycle. If you are in Arm 4, you will take lenalidomide by mouth 1 time each day during Days 1-14 of each study cycle. Swallow lenalidomide capsules whole with 1 cup (about 8 ounces) of water. Do not break, chew, or open the capsules.

If you miss a dose of lenalidomide, take is as soon as you remember on the same day. If you miss taking your dose for the entire day, take your regular dose the next scheduled day (do NOT take double your regular dose to make up for the missed dose). If you take more than the prescribed dose of lenalidomide, you should seek emergency medical care if needed and contact the study staff right away. Women who are able to become pregnant that might be caring for you should not touch the lenalidomide capsules or bottles unless they are wearing gloves. Any unused Revlimid® (lenalidomide) should be returned as instructed through the RevAssist® program.

Arm 1:

You will receive bevacizumab by vein on Days 1 and 15 of each cycle. The first time you receive bevacizumab, it will be given over 90 minutes. If you tolerate it well, the rest of the doses will be given over 30-60 minutes.

Arm 2:

You will take sorafenib by mouth 1 time each day of every cycle (Days 1-28). You should take it with a cup (8 ounces) of water, after taking lenalidomide. You should not eat or drink anything other than water for at least 1 hour before or after taking sorafenib.

Arm 3:

You will receive temsirolimus by vein over 30-60 minutes on Days 1, 8, 15, and 22 of each cycle.

Arm 4:

You will receive oxaliplatin and leucovorin by vein over 2 hours on Day 1 of each cycle. You will also receive 5-FU by vein over 22 hours at home on Days 1-2. The drug will be given through a pump that you carry with you.

Study Visits:

At all study visits, you will be asked about any side effects you may be having and about any other drugs you may be receiving.

On Day 1 of Cycle 1, the following tests and procedures will be performed if they were not performed within 7 days before Day 1 of Cycle 1:

• You will have a physical exam, including measurement of your weight and vital signs.
• Your performance status will be recorded.
• Blood (about 1 tablespoon) will be drawn for routine tests.

On Day 15 of Cycle 1, blood (about 1 tablespoon ) will be drawn for routine tests.

On Day 1 of every even numbered cycle (Cycles 2, 4, 6, and so on):

• You will have a physical exam, including measurement of your weight and vital signs.
• Your performance status will be recorded.
• Blood (about 1 tablespoon) will be drawn for routine tests.

At the end of every even numbered cycle (Day 28 for Arms 1, 2, and 3; Day 21 for Arm 4):

• You will have a CT scan, MRI scan, positron emission computed tomograph (PET) scan, or a PET/CT scan to check the status of the disease. If the study doctor thinks it is in your best interest, other types of scans that have not been listed here may also be performed. The study doctor will explain these other types of scans to you in more detail, and you may be asked to sign a separate consent form that describes the scans and their risks in more detail.
• If your study doctor thinks it is needed, you will have either a CT or MRI scan of the brain to check the status of the disease.
• Blood (about 1 tablespoon) will be drawn for tumor markers.

On Day 1 of every odd numbered cycle (Cycles 3, 5, 7, and so on):

• You will have a physical exam, including measurement of your weight and vital signs.
• Your performance status will be recorded.
• Blood (about 1 tablespoon) will be drawn for routine tests.

Pregnancy Testing:

If you are a woman who is able to become pregnant, you will have blood (about 1 teaspoon) or urine pregnancy tests on Day 1 of every cycle, 1 time each week during the first cycle, when you stop taking the study drugs, and 30 days after you stop taking the study drugs.

Length of Study:

You may continue taking the study drugs for as long as the doctor thinks it is in your best interest. You will no longer be able to take the study drugs if the disease gets worse or intolerable side effects occur.

Follow-Up Visit:

Thirty (30) days after you stop taking the study drugs for any reason, the following tests and procedures will be performed:

• You will have a physical exam, including measurement of your weight and vital signs.
• Your performance status will be recorded.
• Blood (about 2 tablespoons) will be drawn for routine tests and tumor marker testing.
• You will have an ECG.
• You will have a CT scan, MRI scan, PET scan, or PET/CT scan to check the status of the disease. If the study doctor thinks it is in your best interest, other types of scans that have not been listed here may also be performed. The study doctor will explain these other types of scans to you in more detail, and you may be asked to sign a separate consent form that describes the scans and their risks in more detail.
• If your study doctor thinks it is needed, you will have either a CT or MRI scan of the brain to check the status of the disease.

This is an investigational study. All of the study drugs are FDA-approved and commercially available for use in various types of cancer:

• Lenalidomide: multiple myeloma and myelodysplastic syndrome
• Bevacizumab: colorectal and lung cancers
• Sorafenib: liver carcinoma and renal cell carcinoma
• Temsirolimus: renal cell carcinoma
• 5-FU: cancers of the breast, pancreas, colon/rectum, stomach, and a type of skin cancer (superficial basal cell carcinoma)
• Oxaliplatin and leucovorin: colorectal cancer

It is investigational to give lenalidomide in combination with each of the other drugs to patients with advanced cancer.

Up to 180 participants will take part in this study. All will be enrolled at MD Anderson.

Inclusion Criteria:

1. Patients with advanced or metastatic cancer that is refractory to standard therapy, has relapsed after standard therapy, or for which there is no standard therapy available.
2. Patients must be >/= 3 weeks beyond treatment with a cytotoxic chemotherapy regimen, therapeutic radiation, or major surgery. After targeted or biologic therapy there should be 5 half-lives or three weeks, whichever is shorter. Patients may have received palliative localized radiation immediately before or during treatment, providing radiation is not delivered only to the site of disease being treated under this protocol.
3. Eastern Cooperative Oncology Group (ECOG) performance status </= 2
4. Patients must have normal organ and marrow function, defined as absolute neutrophil count >/= 1,000/mL; platelets >/=50,000/mL (unless these abnormalities are due to bone marrow involvement); creatinine clearance >/= 50 ml/min by Cockcroft-Gault formula; total bilirubin </= 2.0; and alanine aminotransferase (ALT)/ serum glutamic pyruvic transaminase(SGPT) </= 5 X upper limit of normal (ULN) (unless patient has liver metastases).
5. All study participants must be registered into the mandatory RevAssist® program, and be willing and able to comply with the requirements of RevAssist®.
6. Females of childbearing potential (FCBP) must have a negative serum or urine pregnancy test with a sensitivity of at least 50 milli-International unit (mIU)/mL within 10 - 14 days prior to and again within 24 hours of prescribing lenalidomide (prescriptions must be filled within 7 days) and must either commit to continued abstinence from intercourse or begin TWO acceptable methods of birth control, one highly effective method and one additional effective method AT THE SAME TIME, at least 28 days before she starts taking lenalidomide. FCBP must also agree to ongoing pregnancy testing. Men must agree to use a latex condom during sexual contact with a FCBP even if they have had a successful vasectomy.
7. Patients must be able to understand and be willing to sign a written informed consent document.
8. Must be >/= 18 years of age.

Exclusion Criteria:

1. Any serious medical condition, laboratory abnormality, or psychiatric illness that would prevent the subject from signing the informed consent form.
2. Uncontrolled intercurrent illness, including, but not limited to, uncontrolled infection, uncontrolled asthma, need for hemodialysis, need for ventilatory support.
3. Pregnant or breast feeding females. (Lactating females must agree not to breast feed while taking lenalidomide).
4. Use of any other experimental drug or therapy within 21 days of baseline.
5. Known hypersensitivity to thalidomide.
6. History of hypersensitivity to any component of the formulation.
7. The development of erythema nodosum, if characterized by a desquamating rash while taking thalidomide or similar drugs.
8. Patients unwilling or unable to sign informed consent document.
9. Uncontrolled systemic vascular hypertension (Systolic blood pressure >140 mmHg, diastolic blood pressure > 90 mmHg on medication) for patients treated in the bevacizumab or sorafenib arms.
10. Patients with active deep venous thrombosis or pulmonary embolism or patients receiving anti-coagulation.
11. Patients with clinically significant cardiovascular disease: History of cerebro-vascular accident (CVA) within 6 months; Myocardial infarction or unstable angina within 6 months; Unstable angina pectoris.
12. Uncontrolled intercurrent illness, including, but not limited to, ongoing or active infection requiring parenteral antibiotics on Day 1.
13. Major surgical procedure, open biopsy or significant traumatic injury within 28 days prior to Day 0 of protocol treatment.
14. Patients that are taking CYP3A4 inducers and/or inhibitors, being considered for the temsirolimus arm: If a patient has a history of taking CYP3A4 inducers and/or inhibitors prior to enrollment on the temsirolimus arm, it is strongly recommended that the patient stops the drug and waits at least 5 half-lives of said drug before initiating therapy on the temsirolimus arm.