Skvare has worked with a number of CiviCRM implementations with data sets of significant size. As has been mentioned, do expect to have a bit of a "learning" curve - especially with the LAMP stack setup. It will require a well-tuned VPS.
Data handling will be another major challenge. First, small variations in addresses, prefix or suffix fields, etc. Standardization will be very important and will need to have pre-defined rules akin to a style guide for designers. That may include corrections of character sets, capitalization, and more.
Next, the built-in GUI import tools are not suitable for large and complex imports. We now have an internal library of methods that use Drupal's batch API with the ability to source the data, manipulate it according to established standards, and then insert it into appropriate fields within CiviCRM including the necessary conditions/dependencies/relationships.
Lastly, the number of contacts in a database is not a good indicator of the above requirements. 250K contact records with sparse related info will be a very different setup (both in ongoing server requirements and during data import) from 250K contact records with 30 years worth of contributions, memberships, event registrations, activities, relationships, groups/tags, etc.
As an option, we've also set up CiviCRM to interface with a 3rd party CRM from which the client wished to migrate off. Using the API we were able to dynamically pull data into CiviCRM upon specific user action (ie login, membership renewal, event registration), have the user validate/correct it, and then store it and mark it in the "old" CRM system as migrated. Depending on the level of user engagement that may be a longer timeline but the approach successfully crowd sources the "elbow grease" responsibility for cleaning up data.
Bottom line - CiviCRM is up to the task; the variable aspects for scaling it to accommodate large record sets is mostly a factor of organizational approach and methodology for data management.