Hmm...I use goSMS myself, and haven't ever used Handcent, so I can't really speak to whatever settings may be affecting it. Hopefully someone else might have some insight, as to what might be hanging it up. I know I've had issues sending a full 8 MB pic to another upper phone (Droid X at the time). I don't know if he had any incoming file size limits set in anything, but I had to make sure I always sent him a low res picture instead. I would say make sure you don't have a small "Maximum Message Size" set in the stock messaging app, but you said the flip was having issues too. The minumum size in the stock settings is 200k, so I doubt they were over THAT, so..I'm at a loss atm.
EDIT: One more thought, does it give you any thumbnails or anything? I know when I have low service, sometimes it won't download on mine, and it gives me a "download" button to click, though it generally takes better service to download.
Which does remind me, just for kicks, double-check the Stock Messaging App settings, just to make sure nothing jumps out at ya (if you haven't already)