The 40mA current limit is the Absolute Maximum that an I/O pin on the ATmega328P can supply. Vcc on the ATmega can draw up to 200mA.
From page 313 of the datasheet:

The 5V that connects to Vcc and powers your chip comes from one of two places. Either the USB connection, which in most cases is limited to supplying 500mA. Or an external power supply (wall wort or otherwise) which can supply as much current as is labeled on package.
Vin is your external power supply if connected. USBVCC is your USB power if connected. +5V is whichever has a higher voltage.
You seem to be interested in using an external power supply to run your Arduino and a motor. No problem. You just need to branch off of Vin before the regulator that turns Vin into +5V and powers your chip.
Have a look at this Motor Shield tutorial by Adafruit. In the below diagram, they are powering a motor off of a +9V Vin. In this diagram they are branching off before IC1 which is a 78L05Z. On your Duemilanove, this should be IC4, an MC33269.

This way the motor can take as much current as it wants from your external supply. And the AVR microcontroller can take as much current as it wants and be protected from any nasty spikes the motor puts on the line by the MC33269 voltage regulator.