Andrew
there are some other resources that may be helpful to you. This blog Create rectangular features using their geographic extents | ArcGIS Blog references a tool for creating a feature class for the neatline of the map (vs. the collar) if you have or can create a table of appropriate metadata.
There is also a tutorial available at http://esriurl.com/12218 including a link to the Quad-G software that can automatically identify the tic marks on a map. If you want to work through that tutorial, there is a project folder (with MXD, GDB, tools, metadata, etc.- 540 KB data volume) here http://esriurl.com/12216 and sample data here (5.4GB) http://esriurl.com/12217
Let us know if these do not represent the type of data you have...
Cody B.