My hovercraft is full of eels

A gross perversion? Probably not. The HTTP/1.1 spec is pretty open when it comes to the Accept-Ranges and Range headers:

*The only range unit defined by HTTP/1.1 is "bytes". HTTP/1.1 implementations MAY ignore ranges specified using other units.*

The problem is in getting the clients to send Range headers with their requests.

Indeed. When I read the spec it seemed to imply I could use it to do exactly what I wanted and when the client is a Javascript application sending XML HTTP Requests that's pretty easy to achieve.

I can hear the sound of bob marley in the background, and see thick smoke. This would be a RESTafarians dream ;)

The more I think about it the more I like it. The only thing you don't get is bookmarkable pagination but as I stated in my earlier comment, I'm really not trying to support full-page refresh browsing. I'm more interested in supporting rich-clients using RESTful APIs over HTTP.

When discussing "rich clients", you're talking about returning records x pages of y records at a time. Do you just leave y up to the application?

It seems that we'd be better served by only using this header to specify which records to return, not pages.

Not sure what I'm talking about hehehe. I was more exploring the possibilities :) I agree that record is a more appropriate level of granularity but I wanted something else for comparison.