VocaDB

From their website: "VocaDB is a free to use database for discography information about Vocaloid and related voice synthesizers such as UTAU."

I'd say this is one of if not THE most useful resource you have. VocaDB has over 500,000 songs in its database, so the chances of you finding at least something that can help your search is high.

Generally, the most valuable information you can get, in order of importance, is 1. whether or not the song is actually lost, and if it has a known reprint, 2. a song's NicoNico ID, 3. a song's publish date and 4. a song's duration (among other things).

Tips and Tricks:

Finding if a song is on VocaDB:

1. The easiest way is to just search for the song's name. Be careful of finding songs with the same name but by different producers though.
2. Didn't work? If you a song's NND link? Try pasting it into VocaDB's "Submit Song" page. Wait a few seconds. If it pops up saying "This PV has already been added to the database." then it should give you a link and there's your song. Usually, this will also come along with some info being filled out in the name and producer fields.
3. Song link didn't work? Try using the nicolog entry for the song, then follow the same steps as the above step.
4. If none of this worked, you can see if the producer is on VocaDB, and look through their song entries to see if they have one that matches what you're looking for.