Well, I have posted my paper to CoRR (see arXiv:cs.LO/0505034). (Can someone please register an This document has been dedicated to the public domain. I have also submitted a copy to the university WebDOCs. This version is under a Creative Commons attribution license.arXiv URN scheme?)
After this I transferred my copyright to Springer, modifying their form a little. I only transferred my copyright to the extent possible, and I removed the discount I would get on their books. I also attached a letter informing them of the above submissions. So now I think the worst they can do is refuse to publish my work. We shall see.