You cannot re-arrange IE's toolbar layout. IE manages it, and users can customize it using the built-in UI, but you can't. Sorry.
Actually you can, as you've noticed that the layout is persisted in a binary format in the registry, but it involves a lot of reverse engineering of binary data that may or may not be stored in the registry and since it's an undocumented implementation detail, the IE team can (and actually does) change how it works in every new version of IE. You'd have to write the code three times: once for IE6, once for IE7, once for IE8. And again for IE9 when it ships, and there's no certainty it would be the same anyway. Each one uses a different format and has different rules about when data and how the data is persisted. And forget about the upgrade scenarios.
So, tell whoever made that requirement that you can't do it.
No really, push back. I've actually been on both sides of this equation; I was on the IE team and saw the disasters that extensions caused when they tried to do this, and I've been at companies who had the same requirements and I've done the reverse engineering and tried to keep it working. Trust me, you don't want to do this.