If you are connecting to CRM Online with a Live ID, you need to register a Device ID and Device Password when using the organization service from an outside caller.  I walk through this in my Connecting to CRM Online from an outside caller post.  Thanks to some internal discussions with folks on the SDK team, I discovered a simpler way that doesn’t require manually registering and putting the DeviceId /DevicePassword in the config file.  First you’ll have to download and use the Helper Code: DeviceIdManager Class from the SDK.  In addition to the references from the previous post, you’ll need to add references to System.Security.dll and System.ServiceModel.dll to get it to build.  Once you have done that, you can eliminate the DeviceId and DevicePassword settings from the connection string:

<connectionStrings>
    <add name="CrmOnline" connectionString="Url=[YOUR_CRM_ORG_URL]; Username=[YOUR_LIVE_ID]; Password=[YOUR_PASSWORD];"/>
    </connectionStrings>

You can now connect to CRM Online like so:

var connection = new CrmConnection("CrmOnline");
connection.DeviceCredentials = DeviceIdManager.LoadOrRegisterDevice();
var context = new XrmServiceContext(connection);

DeviceIdManager.LoadOrRegisterDevice() automates the manual steps from the Connecting to CRM Online from an outside caller post.  I’m pretty sure it requires full trust, but haven’t taken the time to confirm.  If you have, leave me a comment to confirm/correct.

@devkeydet