I would reccomend using XFCE instead of MATE. While I don't have that old of a laptop, my desktop PC is running Mint 16 XFCE with a pentium 4 processor (although its at 3.2 ghz) and 2gb of ram. For me, it (XFCE) runs really fast! For me, Cinnamon felt sluggish on my computer, and in fact the login screen would lag and hang. So, I'm thinkng that XFCE may be worth trying, because it is faster. I will see if I can find something relating to changing desktop environments for you.
If you know how to, you could install just a window manager and any application that you would need. Though that would be somewhat complicated, and I couldn't help you there. However, the speed of the computer should increase a lot, so it would also be worth keeping your options open.
As for tweaking, I love to tweak things (until they break, then I have to fix it...
) so maybe in a week or so of experimenting with XFCE on my desktop I might be able to find something to help you speed up the computer even more. The most common things would be removing startup programs (which you've done), disabling anything else you know you will never need (for instance, virtualBox, which you have also done) and potentially cleaning out the dust. A good dusting can really make a difference if heat is this issue.
As far as other distro's/DE's, I'd do some research into which one is fastest, and which one suites your needs. I've heard of puppy linux, though I have no idea what that really is.
As far as RAM is concerned, I don't know how easy or convienent it would be to find compatible ram, let alone upgrade in a laptop. Just trying to open my 1 year old laptop was a nightmare and a half, and laptops have so much space issues... If you can upgrade the RAM, I'd say go for it.
All in all, I'd use what works best for you. If you have any other questions, don't hesitate to ask!
