There are many examples of using REST with simple data models. For example a customer with 5 properties and a collection of orders with 6 properties. However I have a hard time visualizing using REST against a model that is more complex -- that you may find in government procurement, finance, medical records management etc. Are there examples of REST being used as the primary API into a large LOB environments.
Perhaps I'm asking too much from the REST approach?
REST is suitable as long as there is a reasonable descriptive path to describe the data you are wishing to reach.
REST doesn't feel as RESTful when what you're trying to accomplish is publish an API, BUT, I would note that APIs which have been developed using REST philosophy have been really successful.
From your description, you are working with data, which should adhere very nicely to REST, not matter how complicated the structure is. REST does not prohibit publishing schemas, so you may want to consider that as well.
REST is an architectural style, not a representation of the data. Generally today the data is represented in either XML or JSON, which have been battle tested and can easily support the large complex models you are referring to.
In its most basic form, REST is simply the HTTP verbs to control a "resource". The representation of that resource can be as simple or as complex as you need it to be. The CRUD and list operations being the most straight forward. Additional, more complex APIs can also be generated easily within this context.
I am building a REST interface that currently has more than 250 resources. By the time I am finished I expect to have more than a 1000. This is an ERP application that covers accounting, inventory, sales, labour costing, engineering, etc.
The size or complexity of a single resource is not directly related to REST but more a concern of the media types. I chose to take the route of defining my own media type as I am building the client also and the interface is not for public consumption. Choosing the best media type for your situation is probably one of the hardest parts of designing a REST interface.
Unfortunately, most people seem to punt on the media/type decision and choose generic application/json or application/xml and then use downloaded javascript in the browser to interpret the format.[1] That works as long as the only client you have is a browser and you don't want anyone else to re-use your interface. For me it seems to defeat one of the main goals of REST, i.e serendipitous re-use due to loose coupling and standardized formats.
To further explain what I mean by this, consider the case where you deliver application/json or application/xml to a client application. As soon as the client application reaches into that generic format and grabs out a specific piece of data you are creating hidden coupling between the client and the server. If instead you use the media format "application/vnd.mycompany.myformat+xml" you are explicitly defining a contract with the client. This has a huge advantage when you make changes to the format and you have the option to create "application/vnd.mycompany.myformatV2+xml"
People perceive REST to be a loosely specified interface but in actual fact it is not. A REST interface should be very explicit in the precise media types it returns and expects to receive. The media types are the contract. If you receive application/xml and use client code to pull out /Customer/Name you are breaking the contract.
Web applications that use downloaded javascript can consume "application/xml" because the details of the contract are not compiled into the client. However, the client's behaviour is extremely limited to doing whatever the javascript has been preprogrammed to do. Unfortunately, the majority of public RESTful interfaces ignore this constraint and people build clients that are tightly coupled to an unspecified contract. That's why when Twitter changes its format, many of the clients break.