The My Unresolved Items page allows you to assign an item to an existing contact/lead, but is there a way to quickly create leads/contacts for each item? Basically the items aren't associated with any contacts in the database but I would like to quickly make a lead/contact out of each one.
You can try Implisit. Implisit connects to your email server as well as your Salesforce, and enters all relevant emails and calendar events into Salesforce fully automatically, attaching them to Opportunities, Accounts, Contacts and Leads. Implisit also automatically creates new contacts from email interactions.
DISCLAMER: I work for Implisit.
Unless your administrator has Quick Create turned on for your org, there is no way to do this. With Quick Create turned on, you'll see a "New" button when you use the lookup field (click the magnifying glass icon), which allows you to create a new record on the fly. However, many administrators turn off this feature, because it causes data quality problems.
You always have the option of not assigning the task/email/event to a record by using the "Don't Assign" radio button. Otherwise, you'll have to create the new records first and then fix your unresolved items list.