My PDF happened to fit 21 rows per page, so I made sure the current row MODULO 21 equaled 0. Notice I start with a new table each page, so I put the new <table> along with only a <thead> inside the <cfif> after using the closing tags of </tbody> and </table> for the previous page's table and the pagebreak. Then I follow it with the <tbody>, and voila, it works like a charm. I also added a nice footer to the PDF just for funsies.
<cfquery name="getDeletedBarcodes" datasource="#application.dsn#">
    SELECT * FROM deletedRecords
</cfquery>
<cfdocument filename="reports/DeletedBarcodes.pdf" format="PDF" overwrite="true">
    <cfif getDeletedBarcodes.RecordCount NEQ 0>
        <h2 align="center" style="text-decoration: underline; font-weight: bold">Deleted Barcode Records</h2>
        <table class="deletedBarcodesTable" border="1" style="margin-top: 10px" rules="rows">
            <thead>
                <tr>
                    <th>Barcode</th>
                    <th>Building</th>
                    <th>Room</th>
                    <th>Location</th>
                    <th>Shelf</th>
                    <th>Inventoried</th>
                    <th>Deleter Name</th>
                    <th>Time Deleted</th>
                    <th>Reason Deleted</th>
                </tr>
            </thead>
    <cfelse>
        <p>There are no records to show that have deleted barcodes.</p>
    </cfif>
    <cfloop query="getDeletedBarcodes">
        <cfoutput>
            <cfif getDeletedBarcodes.currentRow MOD 21 EQ 0>
                </tbody></table>
                <cfdocumentitem type="pagebreak" />
                <table class="deletedBarcodesTable" border="1" style="margin-top: 10px" rules="rows">
                    <thead>
                        <tr>
                            <th>Barcode</th>
                            <th>Building</th>
                            <th>Room</th>
                            <th>Location</th>
                            <th>Shelf</th>
                            <th>Inventoried</th>
                            <th>Deleter Name</th>
                            <th>Time Deleted</th>
                            <th>Reason Deleted</th>
                        </tr>
                    </thead>
                    <tbody>
            </cfif>
            <tr>
                <td align="center"><cfif NOT StructKeyExists(getDeletedBarcodes, "Barcode") OR NOT len(Barcode)><strong style="color: red">N/A</strong><cfelse>#Barcode#</cfif></td>
                <td align="center"><cfif NOT StructKeyExists(getDeletedBarcodes, "Building") OR NOT len(Building)><strong style="color: red">N/A</strong><cfelse>#Building#</cfif></td>
                <td align="center"><cfif NOT StructKeyExists(getDeletedBarcodes, "Room") OR NOT len(Room)><strong style="color: red">N/A</strong><cfelse>#Room#</cfif></td>
                <td align="center"><cfif NOT StructKeyExists(getDeletedBarcodes, "Location") OR NOT len(Location)><strong style="color: red">N/A</strong><cfelse>#Location#</cfif></td>
                <td align="center"><cfif NOT StructKeyExists(getDeletedBarcodes, "Shelf") OR NOT len(Shelf)><strong style="color: red">N/A</strong><cfelse>#Shelf#</cfif></td>
                <td align="center"><cfif NOT StructKeyExists(getDeletedBarcodes, "Inventoried") OR NOT len(Inventoried)><strong style="color: red">N/A</strong><cfelse>#LEFT(Inventoried, 10)#</cfif></td>
                <td align="center"><cfif NOT StructKeyExists(getDeletedBarcodes, "DeleterName") OR NOT len(DeleterName)><strong style="color: red">N/A</strong><cfelse>#DeleterName#</cfif></td>
                <td align="center"><cfif NOT StructKeyExists(getDeletedBarcodes, "TimeDeleted") OR NOT len(TimeDeleted)><strong style="color: red">N/A</strong><cfelse>#TimeDeleted#</cfif></td>
                <td align="center"><cfif NOT StructKeyExists(getDeletedBarcodes, "ReasonDeleted") OR NOT len(ReasonDeleted)><strong style="color: red">N/A</strong><cfelse>#ReasonDeleted#</cfif></td>
            </tr>
        </cfoutput>
    </cfloop>
    <cfdocumentitem type="footer"> 
        <cfoutput>
            <div style="border-top: 5px solid black; border-top-width: 100vw">
                <span style="left: 0; float: left">#DateFormat(Now(), "full")#</span>
                <span style="right: 0; float: right">Page #cfdocument.currentpagenumber# of #cfdocument.totalpagecount#</span>
            </div>
        </cfoutput>
    </cfdocumentitem>
</cfdocument>