I have a new directory site .. which i bought the domain on 4/2/2006 and seting up the server thingy on the next day .. and now it's already in the google SERP I must say that google is fast .. just use some backlinks with good PR and you are on the go ! Planning to bring the PR up to atleast 5 before i accept paid inclusion
Nothing new about this. This is called the google "freshbot" you'll notice your site bounce in and out of the index for quite some time until it can get a stable and balanced stronghold.
I think you will find a hard time to have paid inclusion for a general directory. The amount of time it will take you to make sure all the subcategories have that PR5 will not justify the charge. With so many paid inclusion options out there, I think a lot of directories are folding up (as mentioned in an earlier thread)