The problem is that the Duemilnove seams to be be powered by the Mega even if there is no external power on the Duemilnove.
This is quite common, the tx signal is powering its host chip through the ESD protection diodes. All (most) pins have a diode from the pin to VCC to shunt ESD pulses, however it also provides a path for normal Vs to VCC and therefor the entire circuit board.
The funny thing is that when in this state I can communicate fine between the two boards but when I connect power to the Duemilnove no transmission can be done.
The above doesn't explain this, as CR said, you really have Tx->Rx and Rx->Tx don't you?