I managed to resolve the issue. Turns out the underlying table did not have primary key defined, so all the NOT NULL columns (including two DateTime columns) inferred Entity Key properties in the Entity Framework entity for that table. After setting "Entity Key" property to False for these two properties everything started to work as it should.
This is not a universal solution, but more of a workaround for this particular case, where rows are uniquely identified by other columns than those with DateTime type. If I really had a table where DateTime column would be the primary key, I guess I would run into the same issue again.
Regarding FormatException, setting <globalization culture="en-US" />
in web.config under system.web node fixed it, but after removing the Entity Key property from the DateTime columns even this was unnecessary, since DateTime values were not used to construct the URI anymore.