I just tested my concept and it works on my system.
After you set the restrcitions page did you also stop and restart the IMS services?
There have been occasions when the registry is not properly updated and all of the Exchange services needto be restarted to enforce a change (this is usually rare to use this as a last resort)
Also to help enforce it, create another group place all users that will have the ability to send Internet messages and place them in the Accept Messages from.
When you received the message on the Hotmail account, were you able to reply back? If so then you need to remove all SMTP Proxy addresses from the email tab of the Mail account.
Also ensure that your IMS Server is bug free, should be at NT4/SP6a with secuirty patches and Exchange 5.5/SP4 with SMTP security patch.
Good luck.