Found the problem.
The standard metadata string looks like this:
metadata=res://*/Model.csdl|res://*/Model.ssdl|res://*/Model.msl
And this works fine in most cases. However, in some (including mine) Entity Framework get confused and does not know which dll to look in. Therefore, change the metadata string to:
metadata=res://nameOfDll/Model.csdl|res://nameOfDll/Model.ssdl|res://nameOfDll/Model.msl
And it will work. It was this link that got me on the right track:
http://itstu.blogspot.com/2008/07/to-load-specified-metadata-resource.html
Although I had the oposite problem, did not work in unit test, but worked in service.