I agree with Jacob that this is a VBI, but the following should help you.
To rlogin/rcp/rsh to a machine without enter a password, you should have $HOME/.rhosts file defined on the target machine if you are trying to login as root. If you try to login as non-root, make sure the user is in /etc/passwd and the host you are login from is defined in either /etc/hosts.equiv or $HOME/.rhosts files. Both /etc/hosts.equiv and $HOME/.rhosts file should contain the host name that are allowed to connect. Optionally, you can associate a user name with that host name to narrow the permission to just those users. So, the format should look like th following line:
Both rsh or rlogin prompt for a password. All you need to do is open /etc/hosts.equiv file on host system and add entries for all hosts you would like use without password .
This file list of hosts and users that are granted "trusted" r (rsh/rloging) command access to your system without supplying a password.
$ cat /etc/hosts.equiv
In above file "a" and "b" hosts can connect without a password.
Caution: R (rsh/rlogin) commands are very insecure if possible switch to secure shell (ssh). You can configure ssh so that is does not prompt for a password.
Based on your edits, I'm pretty sure that you are connecting from Server 2008 to an AIX box. I'll bet that since this worked fine in 2003, you are using the MS default install, which will NOT let you use a local user to rsh because of changes MS made to IPV6 in their SUA install (interix v6). Remember, Server 2003 did not have IPV6 enabled by default.
First, save yourself some time and disable IPV6 on the network adapter that you are using and see if this sorts everything out. If you need IPV6 (C'mon, really?!) you will need an updated package from interix (the guys who made the SUA for MS) so that you can get an "updated" version (actually IPV4 only) rsh version from Interix. There are 2 steps:
You need to have the installer pkg installed first and then you can add the package with the command "pkg_update -L rsh".
The pkg installer is not part of the MS installation.
Refer to this web page for more information about pkg: http://www.suacommunity.com/pkg_install.htm
Make sure that you are logged in as a local administrator and that you run the package install and the pkg_update command from the sua prompt.