Redirecting a deleted node

There's a node (page) that I deleted from my site. I have attempted to remove it from Google, but they keep scanning for it. It does this for about 3 hours before it gives in and believes the node isn't there. The only real harm is a really huge log file.

I've tried a lot of the examples I found here on Drupal.org, but none seem to really work. I have a feeling it's the address they are using trying to get at. I'm not sure .htaccess can handle the ?q= part of the line.

http://www.example.com/index.php?q=node/1234&gccid=5810652&gcp=18

The site is on latest 5.x and has clean urls. I have no idea where they got that address from but it is the correct node number that used to exist but it was never addressed that way, always with a clean url.

What I've tried in .htaccess:

RedirectPermanent index.php?q=node/1234 http://www.example.com/newpage

Also:

RewriteBase /
RewriteRule index.php?q=node/1234 /newpage [R=301,L]

(yes, I positioned it BEFORE the clean rewrite rules)

But none have any effect on the redirect and all these get sent to the 404 page.

I'm out of ideas on this. Anyone else have ideas how to fix this? Is there a way (or module) that might let me redirect based on a node number? I haven't seen one yet that does that.

Thanks for your help,
Skip