After more then a month carefully choosing my new cellphone, I choose none of the candidates.
Instead I went with the Sony Ericsson w580i, which actually belongs to the same family as the S500i but has walkman capabilities, and most importantly doesn’t have a fame of cracking the keyboard after less then a week use.
Technically speaking the W580i is an EDGE cellphone that fits my previously mentioned requirements: slide form factor, bluetooth, high-speed modem and costed less then 300€. From the pack of candidate cellphones the grey version of the W580i is also IMHO the most beautiful of them all. So all said I think I did a good buy, but only time will tell as I had only the weekend to test it.