Thank you for posting in Mac forum.
Internet connection is required in order to initiate the remote desktop connection.
For more information on troubleshooting Remote desktop problems, refer to the link below:
http://windows.microsoft.com/en-US/windows-vista/Troubleshoot-Remote-Desktop-problems