Are there cases when mortgage interest is not deductible but debt is still under $750k?

Yes because you probably listed mortgage balances in both 1098's in the the original and the refinance. You only want to enter one mortgage balance and it should be the outstanding balance at the time of the refinance. Enter the first 1098, with the latest mortgage balance and then enter the refinance balance without the mortgage balance listed. This way, the program won't combine both balances. 

Also, there is a question in the interview asking if you mortgage loan is secured by property.  Make sure you say yes in both 1098's because your mortgage loan is secured by your house.