Select a percentage of records using CRM 2011 Dynamic Entity

Question

I'm developing service which consumes CRM 2011 data via dynamic entities (as in, Microsoft.Xrm.Sdk.Entity, the late-binding method). I'm deliberately not using Xrm.cs method (early binding) in an attempt to keep my solution generic.

Also, I want to avoid connecting to a CRM database directly (e.g. EDMX) as this would stop my solution being usable for a hosted CRM (e.g. with no direct DB access).

I have the following (simplified) requirement, I'm really struggling with the selection criteria:

A random 7% of records needs to be selected (and updated).

In SQL, the selection criteria would be relatively easy - I know how to select a random percentage of records. Something like:

SELECT TOP 7 PERCENT * FROM
(
    SELECT TOP 1000 NEWID() AS Foo, [someColumns]
    FROM [someTable]
)
AS Bar ORDER BY Bar.Foo ASC

This works perfectly. I gather the LINQ equivalent is something like:

from e in someEntities
orderby Guid.NewGuid()
select e;

There's a problem though, I don't know of a way to use LINQ with CRM 2011 dynamic entities - instead they insist on using either some restrictive QueryExpression classes/syntax, or fetchXML, as seen on this page (MSDN).

I've identified the following options for fulfilling this requirement:

1. Using dynamic entities, return the whole record set into a List, then simply choose a random selection by index. This however involves returning up to 10,000 records over an internet data service, which may be slow/insecure/etc.

2. Use a fetchXML statement. Unfortunately I don't know fetchXML, so I don't know if it's possible to do things like COUNT, TOP, PERCENT or NEWID().

3. Use Xrm.cs and LINQ, or use a Stored Procedure, or a SQL view. All of these options mean tying the solution down to either direct database connectivity and/or early binding, which is not desirable.

4. Say no to the customer.

Any advise would be greatly appreciated! Can fetchXML perform this query? Is there a better way to do this?