I think this is just because you're not taking into account the space between the </ul>
and the </div>
at the end of your snippet. Allowing whitespace in between the two seems to fix the issue:
// \/
Regex paginationRegex = new Regex("<div class=\"pagination\">.*?<ul>(?<lis>.*?)</ul>\\s*</div>",
RegexOptions.IgnoreCase | RegexOptions.Singleline);
I'm also obliged to mention that regular expressions often aren't the best tool for parsing HTML. Check out Html Agility Pack for a good library that's great at parsing HTML.