Yes it is a dedicated server. Neither bot has a referrer field. I've checked high and low for references to their IPs/User agents and even ran grep on public_html.
If there's any chance you blocked them via mod_rewrite
No, I do the rewrites via .htaccess (checked there too), and I checked the server's root folder (the page that displays if you type the IP in the address bar) and there wasn't an .htaccess present.
you could try running a RewriteLog and see what turns up. Just to confuse you, there's no on/off setting or LogLevel, you just have to specify a file. But it can't be done in htaccess, so you're looking at restarting your server