Finally I got my domain name back. What happened was that it expired without me being notified. The reason I wasn't notified was that the email address that Network Solutions use is ancient and I don't check it anymore. What I had to do was to send a signed fax with a photocopy of me driving license to Network Solutions in the states to tell them to change my email address. Once I've changed my email address I was able to log in and renew the service for three years.
What confused the whole thing was that apparently I thought I could transfer the domain name over to mydomain.com who I use to administer the domain name. The reason it didn't work was that the domain could not be transfered when it was pending deletion.
Long story short: I'm back. To all those of you who have emailed me on mail @peterbe.com you and have got a delivery-error-message, do you want to resend that important piece of email now?
Ah, I had wondered where all my traffic went! (I'm the guy who did that songsearch website oyu linked to a while back; a lot of my referals came from that post :) )