Je suis assez sûr qu'il n'y a aucun moyen de contourner la limite de 256 caractères, Joel Spolsky explique pourquoi ici: http://www.joelonsoftware.com/printerFriendly/articles/fog0000000319.html.
Vous pouvez toutefois utiliser VBA pour se rapprocher de la réplication de la fonctionnalité de la validation intégrée en codant l'événement Worksheet_Change. Voici une maquette pour vous donner l'idée. Vous voudrez probablement le refactoriser pour mettre en cache les ValidValues, gérer les modifications apportées aux plages de cellules, etc ...
Private Sub Worksheet_Change(ByVal Target As Range)
Dim ValidationRange As Excel.Range
Dim ValidValues(1 To 100) As String
Dim Index As Integer
Dim Valid As Boolean
Dim Msg As String
Dim WhatToDo As VbMsgBoxResult
'Initialise ValidationRange
Set ValidationRange = Sheet1.Range("A:A")
' Check if change is in a cell we need to validate
If Not Intersect(Target, ValidationRange) Is Nothing Then
' Populate ValidValues array
For Index = 1 To 100
ValidValues(Index) = "Level " & Index
Next
' do the validation, permit blank values
If IsEmpty(Target) Then
Valid = True
Else
Valid = False
For Index = 1 To 100
If Target.Value = ValidValues(Index) Then
' found match to valid value
Valid = True
Exit For
End If
Next
End If
If Not Valid Then
Target.Select
' tell user value isn't valid
Msg = _
"The value you entered is not valid" & vbCrLf & vbCrLf & _
"A user has restricted values that can be entered into this cell."
WhatToDo = MsgBox(Msg, vbRetryCancel + vbCritical, "Microsoft Excel")
Target.Value = ""
If WhatToDo = vbRetry Then
Application.SendKeys "{F2}"
End If
End If
End If
End Sub