I was doing the math on this 6 months ago - it may have changed a little by now...
Basically, if you're doing more then 30-35 transactions a month, then PayPal is not a good fit (their transaction costs will eat you alive). But if you are doing less then 30 transations a month, then getting the merchant account, SSL, and hassle of creating your own cart will eat you alive (or just be really expensive). Just something to ponder...
A rule I go by when it comes to credit cards:
Never ever never store the credit card numbers. I personally wouldn't even consider trying to encrypt them. I'd just rather not store them at all. Also spend as little time handling the card number as possible (don't be storing it in a hidden form field and passing that all around, for example). Collect the card number, then the next action should be to submit it to the payment gateway and listen for a success/fail response.
If you have to store the card number, I'd recommend only the last 4 digits (the first 4 are somewhat useless depending on the card type). If you have to do re-occurring payments, then setup a "subscription" payment with the gateway and the gateway will handle charging the card each month or time period.
MD5 is one way - so you encrypt the card number, how are you going to unencrypt it? I don't think MD5 is what you want for this.
Email is not secure. Email gets transmitted in raw text. The email will hop along many email servers to get to its destination. At every stop along the way, its possible someone could be packet sniffing or just a nasty server administrator browsing the emails coming and going. Its unlikely it will happen, but its very possible. If you absolutely have to do email, then encrypt it. PGP and there's another one which I forgot - something like GPG should do. A good email client will be able to handle the messages (Moz/Thunderbird appear to but I haven't tried).
As for other services, the only thing I can think of is you build your own. But then you get into coding the interaction with a payment gateway and some server side credit card validation. Its not difficult, but not something I'd recommend for the novice developer (unless they have a really good book or someone to mentor them). The payment gateway may even have you do test payment validation tests and you send the results back to them. Or they may actually access your payment page and do their own validation. Usually they won't let you go "live" until they're happy you're code handles interaction with their server (notice they're NOT going to test your shopping cart to make sure its behaving - just the interaction with their server).