Montevideo GIS
The municipality of Montevideo provides geographic data free of copyright[1].
Street data
There is a shape file describing all streets in Montevideo, and part of Canelones and San Jose[2]. Montevideo's highways are accurate, while Canelones' and San Jose's are pretty inaccurate.
It is possible to filter data from outside Montevideo using the COD_DEPARTAMENTO field. That still leaves some streets outside Montevideo which are all called "CALLE FICTICIA". There are only a couple of dead ends in Montevideo called "CALLE FICTICIA", so these can be filtered without problems.
A C# program (tested in Mono on MacOS X) has been written to transform the shape file to a .osm file. This is available from: http://github.com/maxm/osmuy.
The imported streets have a "mvdgis:cod_nombre" tag that includes the id of the street in the original dataset.