We have produced ultracold, polar RbCs* molecules via photoassociation in a laser-cooled mixture of Rb and Cs atoms. Using a model of the RbCs* molecular interaction which reproduces the observed rovibrational structure, we infer decay rates in our experiments into deeply bound ground state RbCs vibrational levels as high as 5 x 10^5 s^-1 per level. Population in these levels could be efficiently transferred to the vibrational ground state using a stimulated Raman transition, resulting in large numbers of stable, ultracold polar molecules.