<p>We have a .NET web service API. Currently, people use the SOAP definition to consume the API, because we require authentication through a custom Authentication element in the SOAP header. Works perfectly. fine.</p>

<p>SOAP requires the request to be a POST. We want to allow the users to use a the GET verb (so it can be cacheable).</p>

<p>So, what's the best way to offer a simple GET API (doesn't have to be a webservice!) that also offers authentication?</p>

<p>example API route:</p>

<blockquote>
  <p><code>http://www.blah.com/api/Search?query=Foo</code></p>
</blockquote>

<p>Is this an acceptable and common practice?</p>

<blockquote>
  <p><code>http://www.blah.com/api/Search?query=Foo&amp;Key=&lt;some guid&gt;</code></p>
</blockquote>

<p>NOTE: I also don't want to implement SSL nor install extra software or plugins in IIS, etc. etc.</p>

If the web service needs to be secured, and I'm assuming that it does since you currently have an Authentication header, then you should reconsider using GET and not using SSL, at least for the authentication piece.  At a minimum I would POST the authorization request via SSL to the web service/application.  If you don't want to provide authentication on every request, then you will need to accept back (and generate in the service) an authorization cookie that the consumer can use for subsequent requests.
I would avoid using authentication in the URL for exactly the reason that you want to support GET -- if the URL can be cached, then the credentials will be cached as well.  This breaks the security of the web service since anyone can reuse the cached credentials.