Is netatalk on Linux unreliable for hosting Time Machine volumes?

During some discussion on IRC about my recent problems hosting a Time Machine volume on my Linux PC (using netatalk) -- which worked well for a long time but recently developed issues where my Mac kept telling me I needed to start the whole backup over* -- one user stated that doing so is inherently unreliable because Apple's AppleTalk implementation (and maybe Time Machine-specific bits) has certain kinds of error correction built in that netatalk doesn't have. He was quite opinionated about this and strongly encouraged me to use an actual Time Capsule or an external hard drive connected to my Mac.

I haven't run into anyone else who believes this, though, although I have talked to quite a few people who run the netatalk setup and say it works well for them. What substantiation is there to this hypothesis about unreliability and relative lack of error correction?

• EDIT: The exact message is "Time Machine completed a verification of your backups. To improve reliability, Time Machine must create a new backup for you."

Solution 1:

My experience is netatalk is fine until the volume is full and Time Machine starts removing old backups selectively. The deletion process (which involves unlinking a whole load of hard links) seems to be the point at which netatalk falls over and you get the dreaded 'verification' message.

From what I can tell, people who say "it works fine" generally haven't got to the point where their disk is full.

However even external hard drives connected to a AirportExtreme are not immune to this error message. The only completely reliable backup systems I have used are the internal hard drive in an AirportExtreme, and a USB hard drive connected locally.