A lot depends on what format the original hierarchy is stored in. You may find that Jeff Moden's articles on converting hierarchies represented by loop-free adjacency lists to a much more useful table representation based on nested sets, with the usual flattened hierarchy order of the rows specified by a sort path column, gives you a good starting point. The first article is at http://www.sqlservercentral.com/articles/Hierarchy/94040/ and the second at http://www.sqlservercentral.com/articles/T-SQL/94570/, although the second may or may not be relevant depending on what you want to do with the flattened hierarchy once you've got it.

If you use Jeff's technique, I think you just need to (a) ensure that every node is tagged with the appropriate company ID before you start flattening, and (b) execute the technique once for each record with a null uplink (since that will be the top node for a company), passing in the uplink-free node as a starting point. Then you can cluster the union of the results on a sort key consisting of two columns: company ID and sort string. That would probably require some small modifications to the code Jeff has supplied.