I'll speak from the Agile-Scrum perspective. First I need to break down your question into two different problem areas:
1) Definition of Done is an operating agreement on your team. Many teams do not task out their definition of done because it is redundant and not unique to any given user story. A definition of done defines the engineering practices and guidelines used to ensure the functional product is of high quality. When a team estimates a story they should consider the complexity of building a quality solution that incorporates their definition of done. Teams that don't meet their done criteria usually are not good at estimating accurately to leave enough space to build quality into the product. Definition of done usually touches on non-functional areas including:
- Unit Testing practices
- Automated Testing practices
- Manual Testing practices
- Performance/SLA requirements
- Security requirements
- Monitoring requirements
- Documentation standards
2) Finishing tasks doesn't always mean your team has met its definition of done. Don't fall into the trap of seeing a story with all completed tasks and thinking it is done or acceptable. Tasking is both a thought process and a documentation exercise. Highly disciplined teams continuously go through both parts of the tasking processes, most however document tasks up front and then let the actual thought process get out of sync with what was initially documented. "Working software over documentation."
Furthermore, done criteria are often subjective. For instance, ask a developer what "good" unit test coverage is and if 100% is reasonable for all stories. Or what makes a good automated test? What if it breaks during the next iteration?
So how do you handle this in real life. There is no silver bullet, but in Scrum you talk to your team every day about their stories to understand if the team is on track. Teams demo a functional story at the iteration end AND you ask to see things like code coverage, automated test pass rate, and documentation. You regularly talk to your team (during retro or ad-hoc) to understand if they understand the done criteria, see value in them, and if they feel they have enough time to build a quality product. Based on their continuous feedback you identify problem areas like estimation practices, technical gaps, etc and come up with plans to fill those gaps.
You mentioned taking time and budget into account. All done criteria are negotiable AND have an implied cost/benefit. Strong done criteria promote a sustainable product and negate certain risks throughout the life-cycle of your product.
Knowing what the product life-cycle will look like and which risks you cannot afford to take will help you understand where it is appropriate to adjust your done criteria.