I went through the checkout process and used the test Visa number provided by paypal and I did not get an invalid format error.
I used Visa # 4111111111111111 . It is 4 with 15 1's behind it.
I used exp. month 02 and exp year. 2011 and cvv 001
If i put only 2 digits for the year I get an invalid format.
It seems to be working fine. To answer your initial question about the format, it needs to be the entire card number with no dashes, spaces etc. You can try copying and pasting the number above as a test. Make sure you choose Visa as the card type.
I hope that helps.