Another thing to consider is the relative costs of paying it off quickly. Say your interest rate is currently 6% on that $100k and you could pay it off in 10 years (that's a $1110/month payment). Over the life of the loan you would pay $33,224.60 in interest.
Now lets say you refinance at 4% and a 30 year. The monthly payment is $477.42, and if you do the full 30 years you'll pay over $70k in interest (plus the $4500 in closing costs up front). However if pay extra each month (say an additional $622.58 to get it up to the $1110 from before) you'll pay off the loan in 9 years and only pay $19333.41 in interest. For a total cost of $4500+$19333.41=$23833.41 (well, I suppose you should consider the future cost of $4500 paid now, but let's not complicate things too much).
The numbers look even better for a 15 year since the rates are so low for that. At 3.25% and paying extra to get to that same $1110 you'll only pay $13380.45 in interest.
So with the number I gave it does make sense to refinance if you plan to stay in the house that long. With different numbers and different plans it might be cheaper to just apply that $4500 costs right at your current principal.