So, I have received my new (bought used) GPS unit. It's a Mio Digiwalker 168. It came with an 512 MB SD card, but I will upgrade it with a 2 GB card. That should be able to hold quite some tracks as well as maps.
I have managed to make traces and upload them to OpenStreetMap. Looks good.