As I understand it, the usual way for an OData-based service to support 'upsert' (i.e., insert a row, or update it if a row with this key already exists) is through a PUT request that includes a filter for the row and partition keys.
http://myaccount.table.core.windows.net/mytable(PartitionKey='myPartitionKey', RowKey='myRowKey1')
As far as I know, this is how Azure table storage supports upsert. But as far as I can tell, if you try the same thing on your own OData service implemented with the .NET Framework's built-in DataService<T>, this will only succeed if the row already exists. If the row does not exist, I'm getting a 404 error.
In other words, this is only working for updates, not inserts.
I suspect that upsert is simply not supported, but haven't been able to find a definitive answer. Can anyone tell me either how to do this, or confirm that I definitely can't?
You could try and create your own custom query provider (an implementation of IDataServiceQueryProvider). If the user is requesting a single object that doesn't exist and the current http request's method is PUT, return a new one with the given id. I think the built in update provider should be able to handle it from there and update the record. Otherwise you might need your own update provider as well.
Using WCF Data Services Toolkit might make your job easier. Otherwise you'll have to write your own linq provider which sounds like overkill for integration testing.
This is good series of blog posts on msdn describing how to build a custom ds provider.