My last bike that I went to get titled was pretty easy also. It was not in the database at all, anywhere, due to being registered last so long ago. They put it in the computer and as long as it doesn't come up they will give you the title so they can make a buck off of you.
One word of advice, I went to my insurance lady and she got me the bonded title for $100, at the DMV the guy doing the paperwork for me said he thought I paid too much and thought I could get it for $50. So you might want to look around if your insurance company wants to try and take you.