Jimbo,
There are probably a dozen military bases in Germany, and the USPS can be used by anyone who has access to getting on a base - that will be your problem (military ID).
As far as Evian goes - they send it on a container ship. It only takes about 10-15 days to reach the states =) You can do this with DHL if you like, but it's still very expensive for the consumer. Last year I sent a 68 pound monitor to myself from San Francisco and I believe your quote of $500 was about right (i used USPS in the end).
I will be out of the country from August 13-21 for the Olympics so keep that in mind. I may also be moving back to the states in mid-September.
Brian
wikimedia-l@lists.wikimedia.org