We ended up shipping with Stefan Knopf of Knopf Tours (knopftours.com). He has a shipment of bikes going by sea/truck from Orlando to Heidelberg every Spring for about $1000, all included. I was lucky in that a friend of Stefan's was passing through taking his own bike down to Orlando and agreed to take mine down for a very reasonable fee. By the way, before I knew this was an option I had tried soliciting US ground shipping service quotes using uShip.com and had quite a good response. Anyway, this Spring's shipment has already sailed so that's not an option for you this year.
Knopf also offers air shipping to Frankfurt, which isn't as date dependent, for about $1800 from east coast cities. I think the cheapest quote I got for air shipping was from Berklay. I think it was about $1500 via Lufthansa. I tried contacting Lufthansa and Virgin Cargo directly to see if I could save some money by dealing directly with the carrier. Lufthansa told me that I would need to be "dangerous goods certified" and be able to "prepare the documents for this shipment" then referred me to Berklay. Virgin told me that I would be classified as an "unknown shipper", a designation that the TSA prohibits on passenger aircraft.
These are one way prices from US to Europe by the way. It seems that generally shipping from Europe to US is more expensive so you may consider storing with someone like Knopf even after your Spring 2010 ride. The one place I found that was cheaper from EU to US (~$1000 air) had super expensive prices from US to EU (~$2500 air, ~$1300 sea) -- jamescargo.com.
Now that I think of it, you may want to ask Stefan Knopf about his Spring shipments from Heidelberg to Orlando for Daytona bike week.
Hope this helps. Let me know if you have any other questions.