If you attempt to define a GET operation that accepts an entity body with WCF REST like this:

[ServiceContract]
public interface IService
{
    [WebGet(UriTemplate = "/")]
    [OperationContract]
    ComplexFilter Search(ComplexFilter filter);
}

You will encounter the following error:

Operation 'xyz' in contract 'abc' uses GET, but also has body parameter 'lmnop'. GET operations cannot have a body. Either make the parameter 'lmnop' a UriTemplate parameter, or switch from WebGetAttribute to WebInvokeAttribute.

Who says that sending an entity body with a GET request is a bad thing?? RFC 2616 sure doesn't (See here and here). The spec neither explicitly allows (As it does for POST and PUT) or disallows sending an entity body. Interestingly M$ does allows sending an entity body with a DELETE operation even though the the spec for DELETE is just as silent about it as it is with GET, shouldn't it be the same restriction? All that is said in the spec is that GET should be used to retrieve an entity and it must be safe and idempotent. It seems clear that this doesn't rule out sending an entity body. If you have an opinion please leave a comment as I'm really interested in hearing what others have to say about this (Or here regarding this on Microsoft Connect). I could be totally wrong on this one but it looks like sending an entity body with a GET request is indeed RESTful.

UPDATE: Ok, this issue is a little more complex than I thought. Basically there isn't anything that says you cant do this (Like in RFC 2616) but the lack of specific direction in the spec makes it prohibitive. Leonard Richardson kindly gave me some feedback on this and pointed out a few issues:

"It's not illegal in the sense that the server must reject such a request, but it's also not defined. The definitions of PUT and POST say what to do with the entity-body, and the definitions of GET and DELETE don't. So you can do what you want, but you'll have trouble explaining what you mean and operating with other pieces of web machinery.

...because this behavior is undefined, the server can do anything it wants when it gets such a request--including rejecting the request...

The main reason to use GET instead of POST here is that you want the data to be cacheable on the client side or by an intermediary. But if you put selection information in the entity-body of a GET request, I don't think there's a cache in the world that will cache that response correctly."

So if you want to do this you'll need to beware of these issues. It seems like its really not a good idea if the resources are Internet facing (Which is probably the vast majority of RESTful services). You may be able to get away with it in an intranet since the environment will be predictable. All in all its probably a better idea to just use POST and rework your resources (Which Leonard also suggested). WCF was indeed being safe in its implementation so I guess I have to eat my words... :)

Now if you think it's bogus that M$ disallows this don't despair! You can trick the WCF REST API into allowing this. It takes a bit of jumping through hoops though. First you need to create a custom WebServiceHost and factory as follows:

public class WebServiceHostFactory : ServiceHostFactory
{
    protected override ServiceHost CreateServiceHost(Type serviceType, Uri[] baseAddresses)
    {
        return new WebServiceHost(serviceType, baseAddresses);
    }
}

public class WebServiceHost : System.ServiceModel.Web.WebServiceHost
{
    public WebServiceHost(
        Type serviceType, params Uri[] baseAddresses)
        : base(serviceType, baseAddresses) { }

    public WebServiceHost(
        object singletonInstance, params Uri[] baseAddresses)
        : base(singletonInstance, baseAddresses) { }

    protected override void OnOpening()
    {
        base.OnOpening();
        ReplaceBehaviorOnAllEndpoints(this,
            typeof(System.ServiceModel.Description.WebHttpBehavior),
            new WebHttpBehavior());

    }

    public void ReplaceBehaviorOnAllEndpoints(
        ServiceHostBase serviceHost, 
        Type replaceType,
        IEndpointBehavior behavior)
    {
        foreach (var endpoint in serviceHost.Description.Endpoints)
        {
            if (replaceType != null)
            {
                IEndpointBehavior exisitingBehavior = endpoint.Behaviors.FirstOrDefault(
                    b => b.GetType() == replaceType);
                if (exisitingBehavior != null)
                    endpoint.Behaviors.Remove(exisitingBehavior);
            }
            endpoint.Behaviors.Add(behavior);
        }
    }
}

Now create the custom WebHttpBehavior. We're basically creating a surrogate behavior with all the same properties except we set the method to a bogus value. We apply this behavior before the code executes that imposes the restriction (In GetRequestDispatchFormatter). Then afterwards we remove the surrogate and reapply the original behavior.

public class WebHttpBehavior : System.ServiceModel.Description.WebHttpBehavior
{
    #region WebHttpBehavior Overrides

        protected override IDispatchMessageFormatter GetRequestDispatchFormatter(

              OperationDescription operationDescription, ServiceEndpoint endpoint)
        {
            IOperationBehavior originalBehavior = null; 
            IOperationBehavior surrogateBehavior = null;

            TryGetSurrogateBehavior(operationDescription,
                                    ref originalBehavior,
                                    ref surrogateBehavior);

            SwapBehaviors(operationDescription, originalBehavior, surrogateBehavior);

            IDispatchMessageFormatter formatter = base.GetRequestDispatchFormatter(operationDescription, endpoint);

            SwapBehaviors(operationDescription, surrogateBehavior, originalBehavior);

            return formatter;
        }

    #endregion

    #region Private Methods

        private void SwapBehaviors(OperationDescription operationDescription, 

                                   IOperationBehavior remove, IOperationBehavior add)
        {
            if (remove != null && add != null)
            {
                operationDescription.Behaviors.Remove(remove);
                operationDescription.Behaviors.Add(add);
            }
        }

        private void TryGetSurrogateBehavior(OperationDescription operationDescription, 

                         ref IOperationBehavior original, ref IOperationBehavior surrogate)
        {
            if (!IsUntypedMessage(operationDescription.Messages[0]) && 
                operationDescription.Messages[0].Body.Parts.Count != 0)
            {
                WebGetAttribute webGetAttribute = 

                          operationDescription.Behaviors.Find<WebGetAttribute>();
                if (webGetAttribute != null)
                {
                    original = webGetAttribute;
                    surrogate = new WebInvokeAttribute() {
                         BodyStyle = webGetAttribute.BodyStyle,
                         Method = "NONE",
                         RequestFormat = webGetAttribute.RequestFormat,
                         ResponseFormat = webGetAttribute.ResponseFormat,
                         UriTemplate = webGetAttribute.UriTemplate };
                }
                else
                {
                    WebInvokeAttribute webInvokeAttribute = 

                        operationDescription.Behaviors.Find<WebInvokeAttribute>();
                    if (webInvokeAttribute != null && webInvokeAttribute.Method == "GET")
                    {
                        original = webInvokeAttribute;
                        surrogate = new WebInvokeAttribute() {
                            BodyStyle = webInvokeAttribute.BodyStyle,
                            Method = "NONE",
                            RequestFormat = webInvokeAttribute.RequestFormat,
                            ResponseFormat = webInvokeAttribute.ResponseFormat,
                            UriTemplate = webInvokeAttribute.UriTemplate };
                    }
                }
            }
        }

        private bool IsUntypedMessage(MessageDescription message)
        {
            if (message == null)
            {
                return false;
            }
            return ((((message.Body.ReturnValue != null) && 
                (message.Body.Parts.Count == 0)) && 
                (message.Body.ReturnValue.Type == typeof(Message))) || 
                (((message.Body.ReturnValue == null) && (message.Body.Parts.Count == 1)) && 
                (message.Body.Parts[0].Type == typeof(Message))));
        }

    #endregion
}