First of all, don't trust Google too much. Remember that it's used by many non-native speakers. Instead, try to use a corpus, such as
http://www.collins.co.uk/Corpus/CorpusSearch.aspx
But even in Google, the results for ""I regret not to have" are 292, compared to 68500 for ""I regret not having".
In Collins WordbanksOnline English corpus, the results were as follows:
"regret+not+having"
=4 results
"regret+not+to+have"
=0
"regretted+not+having"
=3 results
"regretted+not+to+have"
=0
Thus, we could conclude that "regret not to have done something" is either extremely rare or, more probably, flat out ungrammatical