For others I wonder what the costs of this are in terms of the memory footprint (both RAM and ROM). Are there reference implementations in existence?
Oh, and to complete my answer, no there isn't per-se a reference implementation yet. What exist so far, outside of actual full fledged OF implementations, are IBM PIBS firmware for embedded which implements the full OF client interface, and the kexec tools using the flattened format. The reason why I'm writing this document is precisely to get that developement started as part of uboot. As it was said earlier, no new board support code will be accepted upstream if it doesn't use a device-tree. This decision has been taken a while ago and will not be changed.
There are IBM internal stuffs used for bringup that implement this, so I can confirm it works :) But unfortunately, none of these can be distributed at the moment, and thus they don't constitute a reference implementation.
Ben.