Sealing gap between house and driveway
For raw holding power, sustained flexibility, and general toughness, it's hard to beat modern urethane caulks. Here's a good example (not an endorsement). 

Note that urethane in any form (varnish, caulk, spray foam, household glue) is extremely sticky and will instantly ruin clothing and surfaces if it makes contact. It'll also grab skin and hang tight until it wears away. 

Also, I don't think a heat gun is the right approach to removing your existing caulk unless it's a thin, soft layer. You'll have a hard time getting enough heat into the bead and surrounding concrete to soften it all the way through. Probably better to just scrape it away.