I don't think I really knew what freestyle was until I started reading your blog, but there's one freestyle or freestyle-esque song I've known for a lot longer than that, and which I did know was "Latin" inspired -- Domino Dancing by the Pet Shop Boys.
Side note about freestyle
The story goes that the Pet Shop Boys had written the song and wanted it to have a "Latin" sound, and after hearing lots of Exposé songs during a visit to the US they went to Miami and recorded it with Lewis Martinée.