The municipality of Montevideo provides geographic data free of copyright.
There is a shape file describing all streets in Montevideo, and part of Canelones and San Jose. 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.