I can confirm you are using the right approach. The only reason I can think of to explain why adding a 500ms delay would make a difference is if the element was being added at the time your wait for element not exist was executing. For example:
Step 14 click a button which causes the UI to change, adding the element that step 15 will check
Step 15 Wait for element exists not
Step 15 may unexpectedly pass because it's easy for the test script to outrun the application you're testing. In this case adding the 500ms delay is the right thing to do.
the Telerik team