I just went looking in the Contact Form and found that you can view the IP address from each submission by hitting "View Messages" in the module title, then clicking the "View" button at the bottom left of each submission. Near the bottom you'll see User Agent, Remote Host, Remote Address, and Local Address listed.

In that case it seems most likely that you don't have the form configured to store messages in the database, only to email them. If you click the settings link you mentioned, there should be a checkbox labeled "Keep Messages?" -- make sure that this box is checked. There is also another option labeled "Append Visitor IP to Message?", which should be checked as well for your purposes.

Sorry, I should have mentioned those options earlier it just didn't occur to me that the form you're working on might have been configured away from the defaults already. I hope this helps.