First thing, how fast is your connection? ADSL or dialup or what. you need to know the up speed, not the download speed.
secondly, what else is using the connction? any other pc? are you doing any file uploading/downloading? they all take away bandwidth from outlook.
where is your smtp mail server located, in the same country?
go to this site
http://www.speedtest.net/ and choose a location near your smtp server to run the test from. you can try ruinning on an empty machine and a loaded machine to get 2 different figures.
Then do the sums. work out how long it will take to transfer 4megabytes at whatever bits per second speed you measured.
also, check the timeout figure on the connection - set it to something a bit longer if necessary.
one quirk of outlook, if it gets a fail on an item when sending, that item may not be attempted again until you close down and restart outlook.