I.e., after executing the code and removing the element from the page, it remained in browser memory.
(BTW, I used Google Chrome memory profiler to find out hanging elements).
So, the leak was caused by the Prototype's code, and I found out this nasty line:
Ironically, Prototype tries to avoid memory leak in IE by removing all event handlers on page unload, and for that, keeps a collection of the elements in the CACHE array. But, it never removes elements from the array (only on page unload), even when all event handlers are removed from an element. For any heavy ajax application, when elements are added/removed/replaced on the fly, this may be very unpleasant.
I've fixed the problem in my Prototype fork on GitHub, and added a pull request to Prototype. Hope, it will save someone some hairs.
You can also download patched prototype.js with the fix.
Update: my original fix introduced a performance problem in stopObserving method (when many elements were observed on the page). Now, the problem is fixed, all related resources above were updated.