[Galaxy Tab 10.1 Q&A, Help & Troubleshooting] SheridanJohn:
I was able to retrieve a recovery.img from the full firmware P7501XXLPC_P7501DBTLPC_DBT and create a tar.md5 just from recovery.img via cygwin:

>tar -H ustar -c recovery.img > recovery.tar
>md5sum -t recovery.tar >> recovery.tar
>mv recovery.tar recovery.tar.md5

This flashed ok and anounced itself as Android System Recovery 3e. Factory reset/wipe did format /data and format /cache.

I then flashed recovery.tar.md5 from droidbasement with CWM 6.0.3.0 and flashed CM 10.1 nightly 20130513 via sideload and the gapps gapps-jb-20130129-P75xx.zip from droidbasement.

Afterwards I rebooted into recovery and did an e2fsck on all partitions via adb shell. The e2fsck on /system did return immense amounts of errors:

e2fsck 1.41.14 (22-Dec-2010)
Pass 1: Checking inodes, blocks, and sizes
Deleted inode 15297 has zero dtime. Fix<y>? n
n
no

Inodes that were part of a corrupted orphan linked list found. Fix<y>? yes

Inode 15329 was part of the orphaned inode list. FIXED.
Deleted inode 15349 has zero dtime. Fix<y>? n
n
no

Deleted inode 15361 has zero dtime. Fix<y>? yes

Deleted inode 15377 has zero dtime. Fix<y>? n
n
no

Inode 15381 is in use, but has dtime set. Fix<y>? yes

Inode 15381 has imagic flag set. Clear<y>? n
n
no

Inode 15381 has a extra size (65535) which is invalid
Fix<y>? yes

Inode 15381 has compression flag set on filesystem without compression support. Clear<y>? n
n
no

Inode 15381 has INDEX_FL flag set but is not a directory.
Clear HTree index<y>? yes

Inode 15381 should not have EOFBLOCKS_FL set (size 18446744073709551615, lblk -1)
Clear<y>? n
n
no

Inode 15381, i_size is 18446744073709551615, should be 0. Fix<y>? yes

Inode 15381, i_blocks is 4294967295, should be 0. Fix<y>? n
n
no

Inode 15382 is in use, but has dtime set. Fix<y>? yes

Inode 15382 has imagic flag set. Clear<y>? n
n
no

Inode 15382 has a extra size (65535) which is invalid
....

The other partitions are fine:

~ # e2fsck -fn /dev/block/platform/sdhci-tegra.3/by-num/p5
e2fsck -fn /dev/block/platform/sdhci-tegra.3/by-num/p5
e2fsck 1.41.14 (22-Dec-2010)
Pass 1: Checking inodes, blocks, and sizes
Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Pass 5: Checking group summary information
/dev/block/platform/sdhci-tegra.3/by-num/p5: 15/28672 files (6.7% non-contiguous), 3720/114688 blocks
~ # e2fsck -fn /dev/block/platform/sdhci-tegra.3/by-num/p8
e2fsck -fn /dev/block/platform/sdhci-tegra.3/by-num/p8
e2fsck 1.41.14 (22-Dec-2010)
Pass 1: Checking inodes, blocks, and sizes
Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Pass 5: Checking group summary information
/dev/block/platform/sdhci-tegra.3/by-num/p8: 14/3825664 files (0.0% non-contiguous), 286204/15275644 blocks

I dd'ed /dev/zero over p4 (system) and checked the other partitions again, they were fine. I then reinstalled CM 10.1 and gapps, rebooted recovery and rechecked the filesystem...

~ # dd if=/dev/zero of=/dev/block/platform/sdhci-tegra.3/by-num/p4
dd if=/dev/zero of=/dev/block/platform/sdhci-tegra.3/by-num/p4
dd: writing '/dev/block/platform/sdhci-tegra.3/by-num/p4': No space left on device
1183745+0 records in
1183744+0 records out
606076928 bytes (578.0MB) copied, 110.833892 seconds, 5.2MB/s
...
~ # e2fsck -fn /dev/block/platform/sdhci-tegra.3/by-num/p4
e2fsck -fn /dev/block/platform/sdhci-tegra.3/by-num/p4
e2fsck 1.41.14 (22-Dec-2010)
Pass 1: Checking inodes, blocks, and sizes
Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Pass 5: Checking group summary information
/dev/block/platform/sdhci-tegra.3/by-num/p4: 1544/37040 files (0.3% non-contiguous), 83490/147968 blocks

Now it was clean after installation...!!

What do you think, should I dd all other partitions like /cache, /data as well? How can this be at all? Flash error that was relocated now?

=> addition:

I thought I will try my luck and reflash the nightly. Afterwards, I again had many file system errors on /system...

BTW: Did you ever try to e2fsck your system partition from recovery? Hardly imagine that it is normal to have file system errors, but who know. My Galaxy Nexus has none, though.