Determine whether an IQueryable<T> has been ordered or not

It's possible. Here's an extension method:

public static bool IsOrdered<T>(this IQueryable<T> queryable)
{
    if (queryable == null)
    {
        throw new ArgumentNullException("queryable");
    }

    return queryable.Expression.Type == typeof(IOrderedQueryable<T>);
}

Yes you can inspect the IQueryable.Expression tree to see if it calls any of the OrderBy/ThenBy methods. Expression trees can be examined by deriving a class from ExpressionVisitor.

There is an internal OrderingMethodFinder in System.Web - which you could adapt. Here's what I came up with:

// Adapted from internal System.Web.Util.OrderingMethodFinder http://referencesource.microsoft.com/#System.Web/Util/OrderingMethodFinder.cs
class OrderingMethodFinder : ExpressionVisitor
{
    bool _orderingMethodFound = false;

    protected override Expression VisitMethodCall(MethodCallExpression node)
    {
        var name = node.Method.Name;

        if (node.Method.DeclaringType == typeof(Queryable) && (
            name.StartsWith("OrderBy", StringComparison.Ordinal) ||
            name.StartsWith("ThenBy", StringComparison.Ordinal)))
        {
            _orderingMethodFound = true;
        }

        return base.VisitMethodCall(node);
    }

    public static bool OrderMethodExists(Expression expression)
    {
        var visitor = new OrderingMethodFinder();
        visitor.Visit(expression);
        return visitor._orderingMethodFound;
    }
}

Use it like so:

bool isOrdered = OrderingMethodFinder.OrderMethodExists(myQuery.Expression);