What licence is required for an external service to call MS CRM via the web services?
Best practice is for your external program to authenticate with the web services using the credentials of a user with a Full/Professional license. A limited license does give some expanded permissions through the API but they are still fairly limited.
More details about the license types: http://www.powerobjects.com/blog/2013/04/11/full-vs-limited-licenses-in-dynamics-crm-2011/