I started to play with point clouds (or point sets) when trying to render some 3D fractals in realtime. After trying with raytracing, marching cubes (polygonal rasterization) and voxel-volume data (both by raytracing and 2D layer composition), I went for point clouds (I think there is no technique I haven't tested on 3D fractals :) ).
My first attempt to point clouds was not raytracing, but point-rasterization with OpenGL. At that time I was not an expert at all in OpenGL, so I hardly got a few thousand points rendered in realtime. Because I used alpha blended sprites (or billboards) to represent each point, I had to render them from back to front order. That means I had to sort the points every frame. You will find the links to those very first experiments in the bottom of the page.
Later, in 2005, I got interested again on point clouds after some discussion with some friend about voxels, point clouds and a well known realtime demo called "We Cell" made by Kewlers. So I remade the pointcloud engine in a two days. This time, the software was able to work in realtime with few millions of points (you can download it here). See screenshots below.
Still, the aproach in this test was relatively brute force. No acceleration structure was used, neither occlusion culling or level of detail. The key for speed was based on two points: models were small enough to fit in video memory (that allows up to ten million point clouds normally), and precomputed back-to-front index arrays for skiping the per-frame sorting of the points. This last issue not only aliviates the CPU time used for the sorting, but also the bus traffic between CPU and GPU, since not every frame the index array must be changed. The big trick comes from the fact that these point clouds where grid aligned point clouds, coming from voxel spaces (regularly sampled volumetric data). For some more information on the implementation and more explanations, see the volumetric sort article.
These are screenshots of the very early point cloud visualizer I made to display the 3D fractals and 3D Perlin noise based turbulences around 2002.