Me and another guy have been trying our best to remove some kind of weird doodad, but just can't get to select it (we've actually spent more than an hour each on that).
It looks like a Point in the editor (the pin thing), except that it is green, isn't listed anywhere, doesn't have any tag/name, and isn't selectable (thus non-deletable).

Any ideas what it is and how to get rid of it?

Sounds like a Terrain Object, you need to click the terrain objects button from the terrain palette to select those and delete them.

If that doesn't work, a screenshot or something would help.

It was indeed a Terrain Object.
What is the purpose of those things?
How are they different from doodads?

They're supposed to actually be doodads, meaning they change the terrain under them instead of just adding some junk on top. Making custom ones is an incredible pain though.