On altavista.com you can test to see if your link has been added by typing the line below into the search field:
If it is listed it will be returned, if not it won't be. You can also check who is linking to you by running this line below:
This returns all the pages from sites that are linking to you. It also gives you the total number of pages, in otherwords matches to your search. The advantage here is that some other search engines appear in the list, so you know then that you have been added to those as well. Also, don't think that by linking to yourself from your own site will help, search engines are well wise to that old trick.
Lots of sites offer tools like this as well, but I can't vouch for their accuracy, I noticed inconsistencies with them, so I stopped using them. I'm sure there are many other ways to.
Personally I totally avoid submission software (unless I'm submitting to ffa sites) for search engines. It's quite well documented that they often refuse to add sites to their listings if they are submitted in that manner. I also read that with free listings they only add those that can add some real value to their listings, but whether that is true or not I don't know. I do know that a lot of these search engines have human editors, that is another reason why free listings take longer, they are basically put to the back of the queue.