Yes new bonds were issued in years without deficits.

This is from Treasuries Direct - History of Marketable Securities Products and Programs

1999 March 1999: Auction results began breaking out how much of the auction was taken down by Treasury Direct.

1999 June 1999: First online submission of noncompetitive customer list into an auction through the Automated Auction Customer List (AACL) application.

1999 Regulations for buying back unmatured debt were finalized.

2000 Constraints on Treasury's ability to reopen securities from original issue discount rules were lifted, as long as the reopening occurs within a year of the original issuance.

2000 March 10, 2000: Treasury held first buyback operation. Buybacks were a result of the budget surplus in the late 1990’s. Buybacks functioned as “reverse auctions” where the Treasury bought back securities to reduce the amount of interest paid.

2000 30-year bond issuance was changed. Original issues were offered in February and then later reopened in August.

2000 30-year inflation indexed bond was reduced to one issuance a year in October.

The U.S Treasury suspended issuance of the 30 year bond between 2/15/2002 and 2/9/2006 but in every other year since 1979 the Treasury sold the 30 year bonds.

The Treasury does not have to need funds to sell bonds. In 2000 the Treasury actually bought back higher yielding bonds and issued new bonds with lower yields to reduce interest payments.

Just because we ran a surplus does not mean we did not need to sell bonds to refinance our existing debt. Bond mature and the principal must be paid, that money usually comes from issuing new bonds.