I think it must be the same couple. I had a look on FamilySearch for the couple on censuses, but they were not there as a couple. There was only one Cornelius HOLMES on England/Wales censuses:
1841 Skirlaugh, Yorkshire: (all HOLMES) Cornelius 50, Henry 14, Robert 10, Elenia 10 (HO107, 1221/6, p4)
1851 Skirlaugh, Yorkshire: (all HOLMES) Cornelius 60, Sarah 40 wife, Dinah 7 daughter, Leavesay Appleyard 1 daughter (HO107, 2365/311, p8)
1861 Skirlaugh, Yorkshire HOLMES Cornelius 74, wid, lodger (RG09, 3605/18, p5)
So, only one Cornelius HOLMES on the England/Wales censuses 1841. The daughter's name on the 1851 census indicates he is your man.
Not all marriage bonds are followed by a marriage, but it seems that Cornelius did marry Charlotte twice. Very strange. If Cornelius' first wife died in 1820 he was a widower not a bigamist in 1825. So, was Charlotte under age in 1825 (requiring parental consent)? This could account for the second marriage a year later over 60 miles away in a different county. Bride and groom being both "of the parish" just means that they had been in residence for a while.
Unless the vicar or parish clerk of St Denis & St George, York were told that the York marriage was not legal there would be no record. Maybe the couple went to Grimsby to 'make it legal' to avoid any possibility of children being labelled as illegitimate?