Can duemillanove read 18 bits and 3 A I/O at 1 millisecond?

I want to read 18 binary inputs and 3 analog I/O readings with a sampling time of 1 millisecond. Is this possible on the arduino duemillanove or do I need to buy the Mega 2560? can neither do it?

You need a Mega but not for the speed but for the IOs. An ATmega328 has 21 inputs maximally but the Duemillanove has just 19. The limiting factor are the analog reads as you get a maximum sample rate of 15kHz on them. With a clever programming (using the analog conversion interrupt) you'll get what you want in under 1ms (don't forget: the processor can do 16000 statements in 1ms).

More of a problem might be what to do with the sampled data. You might have problems getting that resulting data out of the Arduino within 1ms but it's definitely possible if you choose clever data formats.

Uno & Duemilanove have 20 inputs. 14 digital, 6 analog/digital.

Some TQFP 328 boards have 2 additional analog-only inputs as well. Nano perhaps? A6, A7. Not brought out to a connector on the Promini.

Doing 3 direct port reads will take almost no time, 3 analog reads wiil take around 300uS.
1mS is 1000 Hz.
So you've got close to 700uS to do something with 3 bytes and 3 integers of data. Plenty of time.

Uno & Duemilanove have 20 inputs. 14 digital, 6 analog/digital.

Correct, but on pin 13 they have an LED installed (by default), so this can only be an output and not an input.

The Seeeduino is an example of a board that has the two additional A6 and A7 (which are not multiplexed GPIOs BTW).

So you've got close to 700uS to do something with 3 bytes and 3 integers of data. Plenty of time.

If you put the values out in ASCII on a 9600 baud line, it's not enough (that's the usual approach of the un-experienced Arduino programmer).

"Correct, but on pin 13 they have an LED installed (by default), so this can only be an output and not an input. "
Nonsense. A pin connected to a 1K resistor to Gnd (duemilanove, and older Unos) or to the input of a comparator (later Unos) can certainly be used as an input.
Source only needs to have 5mA output current capability.
D13 is also SCK pin for programming when installing a bootloader, and they drive the pin high & low no problem.

meee418 said nothing about outputting the data to anything. You're reading too much into the original post.
Going from there tho:
A faster data rate can always be used if its determined the data needs to go out over a serial port.
The digital inputs can also multiplexed, or sampled with parallel-load shift registers via SPI, and the analog & digital results sent out via I2C or SPI also if needed.