It only redirects people with a referrer from Google (possibly also other search engines.) If I take off the referrer part of curl I just get a normal page back.
curl -e "http://www.google.co.uk/search?q=new+wine+ireland" --include http://www.newwineireland.org/
HTTP/1.1 302 Found
Date: Sun, 20 Nov 2011 11:44:17 GMT
Content-Type: text/html; charset=iso-8859-1
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<p>The document has moved <a href="http://sweepstakesandcontestsinfo.com/nl-in.php?nnn=555">here</a>.</p>
The content of the response (after the headers) suggests that this is an Apache generated redirect and not a PHP generated one. Most people don't think to send a body when using the PHP header() function for redirects and that text matches exactly what an Apache generated body would look like.
Based on this I would suggest looking in Apache config files. Everything in /etc/apache (or /etc/httpd deoending on your distro) needs to be checked. It doesn't have to be a RewriteRule or even a Redirect. It could be an extra Include directive that loads the redirect from another file somewhere else. It could even be a directive that changes what .htaccess files are called.
A command that might help you find it is
grep -r "sweepstakesandcontestsinfo" /etc/apache.
You didn't mention how you checked that it's not a .htaccess redirect. .htaccess is the most likely option because it usually doesn't require any special privileges to write one of those inside the document root.
If you haven't already done so, run this:
find /var/www -name .htaccess but change "/var/www" to your document root.
If that doesn't find anything, try the same command but with / as the first argument. Obviously, you will have to check over each and every line in every .htaccess file you find.
If you find that some of your Apache config files are changed, then this attacker has root access on your box. The best response at that time is to take it offline and begin a proper cleanup. There are many questions on both here and security.SE about how to recover from a compromise once you have cleared up the immediate problem (which is the redirect).