Depois de apanhar muito do Ubuntu consegui resolver o problema.
Ontem, formatei o pendrive e verifiquei o espaço ocupado nele, 4 KB. Em seguida copiei 115 MB de arquivos e verifiquei o espaço ocupado nele e percebi uma diferença de 500 MB, estando como 615 MB em lugar de 115 MB que era o que copiei.
Estando no XP usei um comando chkdsk /f e o XP detectou que havia erros no sistema de arquivos do pendrive, mas não podia resolver por falta de espaço (embora ainda houvesse mais de 3 GB livres).
Formatei novamente o pendrive e repeti o comando chkdsk /f. Dessa vez ele detectou os erros e conseguiu consertá-los. Copiei os arquivos novamente e observei o espaço ocupado, desta vez estava tudo certo, ou seja 115 MB em lugar dos 615 MB anteriores.
Testei com diversos Linux, entre eles o Ubuntu 7.04, 7.10, 8.04 e os Fedora 8 e 9 todos conseguiram ler e gravar sem quaisquer problemas. Embora a luz do pendrive não apague, mas os dados não são corrompidos nem nada.
Percebi que se eu tentar acessar uma partição do Windows (NTFS) e copiar arquivos dela no pendrive ou tentar executá-los diretamente, com o pendrive plugado no Linux, o pendrive é acessado e os dados nele são corrompidos.
Hoje (12/06/2008) comprei um Pendrive Kingstone de 1 GB, só para testar com o Linux, pois não desisto do sistema tão fácil assim. Funcionou perfeitamente sem qualquer problema. O pendrive de 4 GB que me refiro ao problema acima é Memory One (na embalagem dele diz que é compatível com Linux 2.4 ou posterior, vai entender... Mas na verdade ele é INCOMPATÍVEL COM LINUX) e tem horas que não funciona de jeito nenhum e outras funciona corretamente. Recomendo usar somente pendrives da Kingstone para não ter problemas...
Assim sendo, depois de muita luta, finalmente resolvi o problema do meu pendrive com o Linux. Fica aí a dica caso alguém também esteja tendo este mesmo problema.