I figured out a solution: my Tiger city field said "061" for NYC and the field I created in my address table said "61" since Arc automatically removed the zero. Apparently when geocoding without zips as many of the other fields as possible must be EXACT matches to produce candidates, and without the city being an exact match I was getting 100% failure.
I did a number of tests using a very small sample of data and streets and found that as long as all possible fields (to/from addresses on left and right, city, state, and street name) were filled in when creating the locator, it didn't matter if the zip field was designated, left blank, or filled with a set of false zips. However, when only the required information was filled in (to/from addresses on left and right and street name, I believe- Arc is currently frozen so can't make sure), the geocoding failed because it was unable to make a match just based on street addresses themselves, even within a single city. I didn't test to see if both city and state were needed, but I assume that they are, or at least that city was more necessary than state, since everything failed when my two city fields were not exactly the same. I never designated the zip field in the run options for my table, which worked fine since the other fields were able to make the match.
One other problem I had: I was using a table copied out of a shapefile, rather than a straight database, so the FIDs were still included a few times when I imported the table and forgot to delete them. The geocoding wouldn't run unless the name for the FID field was changed slightly. (This was the problem at the time of my March 6 post).
Shawn, I don't know if any of the above will help you (maybe designating more fields would help your success rate?), but I have no idea what's going on with your offsets. Mine worked fine, but it's also not something I'm worried about because I have to hand-adjust the points based on historic data. The only records I could find online related to offsetting problems recommended installing SP2, so you might want to make sure you have that.