The problem could be that you have a number of characters within your CheckoutInstructions that eBay will HTML encode or perform Entity encoding before making the calcuation against the 500 character limit. This will cause the actual character count to go over 500.
An example of such a character is the single apostrophe character: '
This character will be converted to "'" before the character count is performed.
This effectively increases the character count by 4, so every single apostrophe character will actually count as 5 characters instead of 1.
Here is a list of the known characters that are converted and the string that they are converted to:
' - '
" - "
< - <
> - >
& - & (we do not replace & if it used as escape character)
% - %
\ - \
Also, all ASCII characters with values 0-31 and 127 (except 13 == carriage return, 9 == horizontal tab, 10 == new line, line feed, 127 == DEL) are replaced by a single SPACE