Cadillac Repair: 1999 Cadillac Deville overheating, fuel mileage, cadillac deville

Question
What should we check?  Our car is overheating while in idle.  It overheated the other day after sitting while waiting for a train. We brought it home and replaced the thermostat but it still overheats. We even tried taking the thermostat out but it still overheats.  Could it be the waterpump? Any ideas?

Answer
Never ever run a computerized engine WITHOUT the correct thermostat as it screws up all the sensor readings and causes driveability and fuel mileage problems.

Are the cooling fan or fans running in back of the radiator when the temp gets up high ?.