Use Selenium RC directly or Selenium with Robot framework

You are absolutely right that incidental and often changing details in the produced scripts is the biggest problem of record-and-playback automation. You can obviously remove the details from the scripts after recording, but in my opinion it's better to build reusable libraries and code scripts manually from the start.

A good alternative for coding scripts using "real" programming languages is using some higher level automation framework such as Robot Framework that you mentioned. As you speculated, Robot's reusable keywords and also variables make extracting details away from tests very easy. The test cases in SeleniumLibrary's demo illustrates this very well and the demo also shows how to use Selenium through Robot.

You also asked about Sikuli. I've never used it myself but it sure looks interesting. You might be interested on this great how-to that explains how to use it through Robot Framework.

Our company is using Fitnesse, not Robot, to control Selenium however, we have the same problem. We switched from making assumptions about the DOM to only accessing elements by ID. Since this is cumbersome in Fitnesse we are currently working to add a Selenium backend to our own Framework (which previously only had backends for Java and Smalltalk).

So, by requiring that elements with certain ID's are present in the DOM we will of course break our tests if someone removes the elements from the page; however, we found that this behavious is very useful as this enforces the contract the tests made with the implementation and it is a good thing we find missing elements as soon as someone broke the implementation.

In addition, it is good practice to keep UI automation skin-deep: Only test what is present on the page with Selenium and test the business-logic by calling the underlying functions directly.