We have been rigorously searching for automated functional testing solutions recently, and we began with Selenium. The entire reason we decided to search for other solutions was that our application also has dynamic IDs with no other obvious XPath mechanism to identify them. Selenium is unable to identify these elements on the page without some additional knowledge, just as you would be unable to identify these elements on the page if you didn't already know what they are.
If you are controlling the DOM creation, consider adding a unique ID or class to this element.
We recently came across eggPlant from testPlant, and it is an interesting approach to functional testing. It's essentially image based. Other viable solutions are Ranorex or HP's QTP or SmartBear's TestComplete.