I'm pretty sure there is no way around the 256 character limit, Joel Spolsky explains why here: http://www.joelonsoftware.com/printerFriendly/articles/fog0000000319.html.
You could however use VBA to get close to replicating the functionality of the built in validation by coding the Worksheet_Change event. Here's a mock up to give you the idea. You will probably want to refactor it to cache the ValidValues, handle changes to ranges of cells, 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