It's really not easy especially if you're new at the game because it was a lot easier to get sites in and stick during the old days. Like you said, a lot of the places you submit to don't seem to care.
First thing you should do is find a place on Dmoz.org and submit it to an appropriate catergory. Google will definitely find your site from there and give it a ratings boost that it wouldn't have if you submitted it on your own to Google. Yahoo shares the google database. 90% of my site's hits are from these two pages, so it really was barely worth the hassle to submit to altavista, lycos, fast, etc--in fact, I get more hits referred to from taiwanese database thieves than those american search engines. The only point in bothering with altavista and the like is that they give you referral information, unlike google/yahoo, meaning you can tell what people are searching for, rather than just guessing where they arrived through your stats.
So try Dmoz first, and be patient, it seems like Google only gets to my site once every two months or so--though fast and altavista are on it like every other day or so, but their engines are so spammed with gateways and shadowing and all kinds of garbage that legitimate small sites can't really get referrals from them. I don't even have anyone really linking to my page (how google measures popularity) and I still come up first on all relevent searches, so I'm not complaining.